File:Dijkstra negative edge weights error.png

Description
English: Dijkstra's algorithm doesn't work with negative edge weights. For instance, consider the graph: Starting in vertex 1, Dijkstra's algorithm will choose the edge (1,2) setting dist(vertex 2)=1 and edge (1,4) setting dist(vertex 4)=4. dist(vertex 2) is smallest distance, so Dijkstra will choose edge (2,3) setting dist(vertex 3)=2. Smallest distance is dist(vertex 3). Because vertex 4 is the last one visited, it never finds the shortest path from 1 to 3, via 4, with total length 1.
Deutsch: Beispiel, warum negative Kantengewichte nicht zulässig sind: Startend in Knoten eins, wird Dijkstra im ersten Schritt d(zwei)=1 und d(vier)=4 setzen, d(zwei) ist am kleinsten, folglich wird im nächsten Schritt d(drei)=2 gesetzt. d(drei) ist kleiner als d(vier), hat aber keine weiteren Nachbarn. Folglich wird Knoten vier als letztes betrachtet und damit niemals die negative Kante (4,3), da Dijkstra zuvor abbricht.
Date 8/11/08
Source Own work
Author Chin tin tin
File:Dijkstra-negative-edge-weights-error.svg is a vector version of this file. It should be used in place of this PNG file when not inferior.Category:Vector version available
File:Dijkstra negative edge weights error.png → File:Dijkstra-negative-edge-weights-error.svg
For more information, see Help:SVG.
In other languages
Alemannisch ∙ العربية ∙ беларуская (тарашкевіца) ∙ български ∙ বাংলা ∙ català ∙ нохчийн ∙ čeština ∙ dansk ∙ Deutsch ∙ Ελληνικά ∙ English ∙ British English ∙ Esperanto ∙ español ∙ eesti ∙ euskara ∙ فارسی ∙ suomi ∙ français ∙ Frysk ∙ galego ∙ Alemannisch ∙ עברית ∙ हिन्दी ∙ hrvatski ∙ magyar ∙ հայերեն ∙ Bahasa Indonesia ∙ Ido ∙ italiano ∙ 日本語 ∙ ქართული ∙ 한국어 ∙ lietuvių ∙ македонски ∙ മലയാളം ∙ Bahasa Melayu ∙ မြန်မာဘာသာ ∙ norsk bokmål ∙ Plattdüütsch ∙ Nederlands ∙ norsk nynorsk ∙ norsk ∙ occitan ∙ polski ∙ prūsiskan ∙ português ∙ português do Brasil ∙ română ∙ русский ∙ sicilianu ∙ Scots ∙ slovenčina ∙ slovenščina ∙ српски / srpski ∙ svenska ∙ தமிழ் ∙ ไทย ∙ Türkçe ∙ татарча / tatarça ∙ українська ∙ vèneto ∙ Tiếng Việt ∙ 中文 ∙ 中文（中国大陆） ∙ 中文（简体） ∙ 中文（繁體） ∙ 中文（马来西亚） ∙ 中文（新加坡） ∙ 中文（臺灣） ∙ +/−
New SVG image

I, the copyright holder of this work, hereby publish it under the following license:
w:en:Creative Commons
attribution
This file is licensed under the Creative Commons Attribution 3.0 Unported license.
You are free:
  • to share – to copy, distribute and transmit the work
  • to remix – to adapt the work
Under the following conditions:
  • attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
Category:CC-BY-3.0#Dijkstra%20negative%20edge%20weights%20error.pngCategory:Self-published work
Category:Dijkstra's algorithm
Category:CC-BY-3.0 Category:Dijkstra's algorithm Category:Self-published work Category:Vector version available