The Floyd-Warshall Algorithm on Adjacency Matrices and Directed Graphs

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 to vertex is the weight of the shortest path from to in the initial graph. At any step in the algorithm, the -entry in the adjacency matrix gives the algorithm's current estimate of the shortest path from to . You can use the "update number" slider to see how the estimated distances are updated.

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 comparisons in the graph, where is the number of vertices. This method slowly improves the estimated shortest distances until they are optimized.