File:Dijkstra negative edge weights error.png

From Wikimedia Commons, the free media repository
Jump to navigation Jump to search

Dijkstra_negative_edge_weights_error.png ‎(796 × 462 pixels, file size: 21 KB, MIME type: image/png)

Captions

Captions

Add a one-line explanation of what this file represents
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.
File:Dijkstra negative edge weights error.png → File:Dijkstra-negative-edge-weights-error.svg
For more information, see Help:SVG.
In other languages
Alemannisch ∙ Bahasa Indonesia ∙ Bahasa Melayu ∙ British English ∙ català ∙ čeština ∙ dansk ∙ Deutsch ∙ eesti ∙ English ∙ español ∙ Esperanto ∙ euskara ∙ français ∙ Frysk ∙ galego ∙ hrvatski ∙ Ido ∙ italiano ∙ lietuvių ∙ magyar ∙ Nederlands ∙ norsk bokmål ∙ norsk nynorsk ∙ occitan ∙ Plattdüütsch ∙ polski ∙ português ∙ português do Brasil ∙ română ∙ Scots ∙ sicilianu ∙ slovenčina ∙ slovenščina ∙ suomi ∙ svenska ∙ Tiếng Việt ∙ Türkçe ∙ vèneto ∙ Ελληνικά ∙ беларуская (тарашкевіца) ∙ български ∙ македонски ∙ нохчийн ∙ русский ∙ српски / srpski ∙ татарча/tatarça ∙ українська ∙ ქართული ∙ հայերեն ∙ বাংলা ∙ தமிழ் ∙ മലയാളം ∙ ไทย ∙ 한국어 ∙ 日本語 ∙ 简体中文 ∙ 繁體中文 ∙ עברית ∙ العربية ∙ فارسی ∙ +/−
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.

File history

Click on a date/time to view the file as it appeared at that time.

Date/TimeThumbnailDimensionsUserComment
current20:23, 11 August 2008Thumbnail for version as of 20:23, 11 August 2008796 × 462 (21 KB)Chin tin tin (talk | contribs){{Information |Description=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

You cannot overwrite this file.

There are no pages that use this file.

File usage on other wikis

The following other wikis use this file:

Retrieved from "https://commons.wikimedia.org/w/index.php?title=File:Dijkstra_negative_edge_weights_error.png&oldid=482537190"