The Floyd-Warshall Algorithm on Adjacency Matrices and Directed Graphs

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

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.

Contributed by: Adithya Vekatesan and Ankit Goyal (January 2014)
Open content licensed under CC BY-NC-SA


Snapshots


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



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send