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)
File information
Structured data
Captions
Captions
Add a one-line explanation of what this file represents
DescriptionDijkstra negative edge weights error.png |
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.
|
I, the copyright holder of this work, hereby publish it under the following license:
![w:en:Creative Commons](https://upload.wikimedia.org/wikipedia/commons/thumb/7/79/CC_some_rights_reserved.svg/90px-CC_some_rights_reserved.svg.png)
![attribution](https://upload.wikimedia.org/wikipedia/commons/thumb/1/11/Cc-by_new_white.svg/24px-Cc-by_new_white.svg.png)
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/Time | Thumbnail | Dimensions | User | Comment | |
---|---|---|---|---|---|
current | 20:23, 11 August 2008 | ![]() | 796 × 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.
File usage on Commons
There are no pages that use this file.
File usage on other wikis
The following other wikis use this file:
- Usage on de.wikipedia.org
Hidden categories: