File:Dijkstra-negative-edge-weights-error.svg
Summary
| Description |
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. 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. |
| Date | |
| Source | Redrawn in SVG, original PNG Dijkstra negative edge weights error.png by Chin tin tin |
| Author | Stkl |
Licensing
This file is licensed under the Creative Commons Attribution-Share Alike 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.
- share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.
