File:Floyd-Warshall example.svg
Original file (SVG file, nominally 1,324 × 535 pixels, file size: 120 KB)
Captions
Summary
[edit]DescriptionFloyd-Warshall example.svg |
English: Demonstration of Floyd-Warshall algorithm for all-pairs shortest path on a directed graph with 4 vertices. At k=0, prior to the first iteration of the outer loop, the only known paths correspond to single edges in the original graph. At k=1, paths that go through the vertex 1 are found: in particular, the path 2→1→3 is found, replacing the path 2→3 which has less edges but is longer. At k=2, paths going through the vertices {1,2} are found. The red and blue boxes show how the path 4→2→1→3 is assembled from the known paths 4→2 and 2→1→3 encountered in previous iterations. The path 4→2→3 is not considered, because it is already known that 2→1→3 is the shortest path from 2 to 3. At k=3, paths going through the vertices {1,2,3} are found. Finally, at k=4, all shortest paths are found. |
Date | |
Source | Own work |
Author | Dcoetzee |
SVG development InfoField | This file uses embedded text that can be easily translated using a text editor. |
Licensing
[edit]This file is made available under the Creative Commons CC0 1.0 Universal Public Domain Dedication. | |
The person who associated a work with this deed has dedicated the work to the public domain by waiving all of their rights to the work worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law. You can copy, modify, distribute and perform the work, even for commercial purposes, all without asking permission.
http://creativecommons.org/publicdomain/zero/1.0/deed.enCC0Creative Commons Zero, Public Domain Dedicationfalsefalse |
File history
Click on a date/time to view the file as it appeared at that time.
Date/Time | Thumbnail | Dimensions | User | Comment | |
---|---|---|---|---|---|
current | 13:39, 15 May 2013 | 1,324 × 535 (120 KB) | CiaPan (talk | contribs) | Weights corrected for path 3→4→2→1 | |
10:21, 17 December 2012 | 1,324 × 535 (117 KB) | Dcoetzee (talk | contribs) | Improve spacing, alignment (uploaded wrong file before) | ||
10:19, 17 December 2012 | 1,324 × 553 (115 KB) | Dcoetzee (talk | contribs) | Improved spacing, alignment | ||
10:16, 17 December 2012 | 1,324 × 553 (115 KB) | Dcoetzee (talk | contribs) | {{Information |Description ={{en|1=Demonstration of Floyd-Warshall algorithm for all-pairs shortest path on a directed graph with 4 vertices. At k=0, prior to the first iteration of the outer loop, the only known paths correspond to single edges in ... |
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 bn.wikipedia.org
- Usage on de.wikipedia.org
- Usage on en.wikipedia.org
- Usage on fr.wikipedia.org
- Usage on hu.wikipedia.org
- Usage on ko.wikipedia.org
- Usage on ru.wikipedia.org
- Usage on uk.wikipedia.org
- Usage on vi.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 | 1324.3164 |
---|---|
Height | 534.84332 |