Understanding the Floyd-Warshall algorithm

The Floyd-Warshall algorithm efficiently solves the all-pairs shortest path problem for directed and undirected graphs. It can work with negative edges, but cannot detect negative weight cycles like Bellman-Ford. As we will see later, it is much more efficient than running Bellman-Ford for each node and has a much simpler implementation than Dijkstra's algorithm. And so, it is the preferred algorithm for solving the all-pair shortest path problem in most graphs.

Algorithm

The idea behind the Floyd-Warshall algorithm is quite simple. Consider two nodes, s, and t, in the graph representing the source and destination nodes, respectively. The shortest path between these nodes can have 0 or more intermediate nodes. For each such pair of nodes in the graph, the Floyd-Warshall algorithm iterates over all the nodes in the graph and for each node, checks if it exists as an intermediate node in the shortest path between the pair.

We create a two-dimensional distance map where distance[s][t] stores the current shortest path between the nodes s and t. We initialize the map with 0 for the same pair of nodes (where s and t are the same), the weight of the edge if an edge connects the pair and infinite for all the other pairs. This is our base case, where the distance map stores the shortest distance between all pairs of nodes if there are 0 intermediate nodes.

Now, we iterate over the list of nodes in the graph, where in the ith iteration we consider all nodes from 0 to i as intermediate nodes for all pairs of nodes in the graph. In each iteration, we check for every pair of nodes s and t, if adding the node i as an intermediary node reduces the currently known shortest distance between them. We do this by checking if distance[s][i] + distance[i][t] < distance[s][t]. If the distance is reduced, we update the distance map for the node pair s and t to the smaller value, signifying that the currently known shortest path has the node i in it; otherwise, we move to the next pair.