Floyd-Warshall example
Autor/Urheber:
Shortlink:
Quelle:
Größe:
1324 x 535 Pixel (122644 Bytes)
Beschreibung:
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.
Lizenz:
Bild teilen:
Relevante Artikel
Algorithmus von Floyd und WarshallDer Algorithmus von Floyd und Warshall, benannt nach Robert Floyd und Stephen Warshall, ist ein Algorithmus der Graphentheorie. In Floyds Version findet er die kürzesten Pfade zwischen allen Paaren von Knoten eines Graphen und berechnet deren Länge. In Warshalls Version findet er die transitive Hülle eines Graphen. Beide Versionen wurden 1962 vorgestellt und gehen auf einen Algorithmus zurück, den Stephen Kleene 1956 im Zusammenhang mit regulären Ausdrücken veröffentlicht hat. .. weiterlesen