File:Dijkstra-negative-edge-weights-error.svg
From Wikimedia Commons, the free media repository
Jump to navigation
Jump to search
Size of this PNG preview of this SVG file: 400 × 240 pixels. Other resolutions: 640 × 384 pixels | 1,024 × 614 pixels | 1,280 × 768 pixels | 2,560 × 1,536 pixels.
Original file (SVG file, nominally 400 × 240 pixels, file size: 2 KB)
File information
Structured data
Captions
Summary
[edit]DescriptionDijkstra-negative-edge-weights-error.svg |
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 |
This vector image was created with a text editor.
Licensing
[edit]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.
File history
Click on a date/time to view the file as it appeared at that time.
Date/Time | Thumbnail | Dimensions | User | Comment | |
---|---|---|---|---|---|
current | 17:54, 24 August 2015 | 400 × 240 (2 KB) | Stkl (talk | contribs) | User created page with UploadWizard |
You cannot overwrite this file.
File usage on Commons
The following page uses this file:
File usage on other wikis
The following other wikis use this file:
- Usage on de.wikipedia.org
Metadata
This file contains additional information such as Exif metadata which may have been added by the digital camera, scanner, or software program used to create or digitize it. If the file has been modified from its original state, some details such as the timestamp may not fully reflect those of the original file. The timestamp is only as accurate as the clock in the camera, and it may be completely wrong.
Width | 400 |
---|---|
Height | 240 |
Hidden categories: