Floyd-Warshall Algorithm Visualization

How it works:

The Floyd-Warshall algorithm computes shortest paths between all pairs of nodes in a weighted graph (without negative cycles). It works by:

1. Initializing a distance matrix with direct edge weights (or ∞ if no direct edge exists).
2. Iteratively updating the distance matrix using intermediate nodes to find shorter paths.

Algorithm Steps: For each node k, consider all pairs of nodes i and j, and update the distance from i to j if going through k provides a shorter path. It is a simple algorithm, so I have included the pseudo-code.

Another Approach: Alternatively, you can just run Dijkstra from every node, however if the graph is dense this will be a slower method. If you still want to do this, but the graph contains negative weights, you can use Johnson's Algorithm, which just involves running Bellman-Ford first to eliminate negative edges, then repeatedly running Dijkstra.

▶ Play → Step ↺ Reset

            for k from 0 to n-1:
              for i from 0 to n-1:
                for j from 0 to n-1:
                  if dist[i][k] + dist[k][j] <
              dist[i][j]:
                    dist[i][j] =
              dist[i][k] + dist[k][j]