The Floyd-Warshall Algorithm on Adjacency Matrices and Directed Graphs

graph number

1

show adjacency matrix?

update number

This Demonstration uses the Floyd–Warshall algorithm to find the shortest-path adjacency matrix and graph. The algorithm is visualized by evolving the initial directed graph to a complete digraph in which the edge weight from vertex

i

to vertex

j

is the weight of the shortest path from

i

to

j

in the initial graph. At any step in the algorithm, the

(i,j)

-entry in the adjacency matrix gives the algorithm's current estimate of the shortest path from

i

to

j

. You can use the "update number" slider to see how the estimated distances are updated.

Details

Floyd–Warshall is an algorithm that finds the shortest distance between all pairs of vertices. However, it does not specify the paths themselves. Using dynamic programming, the algorithm makes

ΘV

3

|



comparisons in the graph, where

V

is the number of vertices. This method slowly improves the estimated shortest distances until they are optimized.

External Links

Floyd–Warshall Algorithm (Wolfram MathWorld)

Shortest Path Problem (Wolfram MathWorld)

Adjacency Matrix (Wolfram MathWorld)

Directed Graph (Wolfram MathWorld)

Permanent Citation

Adithya Vekatesan, Ankit Goyal

"The Floyd-Warshall Algorithm on Adjacency Matrices and Directed Graphs"
http://demonstrations.wolfram.com/TheFloydWarshallAlgorithmOnAdjacencyMatricesAndDirectedGraph/
Wolfram Demonstrations Project
Published: January 17, 2014