How to find the shortest path between every pair of points in a graph

How to find the shortest path between every pair of points in a graph
Image: Intellect (generated)

In short: The Floyd-Warshall algorithm is a classic dynamic programming tool that calculates the shortest path between all pairs of vertices in a directed weighted graph. By iteratively comparing paths through intermediate nodes, it efficiently refines distance estimates until it arrives at the optimal solution for every possible connection.

At its core, the Floyd-Warshall algorithm functions by systematically improving the estimated distance between two vertices. It considers whether a path through an intermediate vertex is shorter than the current known path. This process repeats, expanding the set of allowed intermediate vertices until all possible paths have been evaluated. The algorithm is remarkably versatile, capable of handling both positive and negative edge weights, provided the graph contains no negative cycles.

The modern implementation, popularized in 1962, uses three nested loops to update a distance matrix. While Robert Floyd is credited with its 1962 publication, the method shares deep roots with earlier work. Bernard Roy published a similar approach in 1959, and Stephen Warshall also introduced a version in 1962 for finding transitive closures. It is also closely related to Kleene's 1956 algorithm for converting finite automata into regular expressions, distinguished primarily by its use of a min-plus semiring.

Correct implementation requires careful attention to the order of the nested loops. The standard 'KIJ' order is essential; misordering the loops, such as using 'IJK' or 'IKJ', will fail to produce correct results for certain graph instances. Beyond finding shortest paths, the algorithm serves other purposes, such as identifying the widest paths in Schulze voting systems or detecting negative cycles. If a negative cycle exists, the algorithm will reveal it by producing negative values along the diagonal of the path matrix, as these cycles allow for paths of arbitrarily small, negative length.

The algorithm's efficiency is defined by its ability to solve all-pairs shortest paths in a single execution. By incrementally building upon previously computed shortest paths, it avoids redundant calculations. While it does not inherently return the path details, simple modifications allow for the reconstruction of the specific routes, making it a foundational technique in discrete mathematics and computer science.

Opens the Intellect+ feed with this card first. Swipe up for the next one.

Sources

To cite this card, link to https://intellectplus.co.uk/app/science-floyd-warshall-algorithm.

How we source, check and correct cards: Editorial standards.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

Finding something worth knowing…