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 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.
Liking the course? Check our discounted plans to continue learning.