liveBook · Manning

Shortest path

As explained in Algorithms Every Programmer Should Know

A shortest path is a path between vertices whose total edge weight is minimal among the paths connecting them.

A shortest path connects two vertices with the smallest total edge weight among possible routes. For all-pairs shortest paths, Floyd–Warshall checks whether routing through each vertex lowers the distance between any pair, producing a global distance lookup table. section 9.0

Negative edges can be included when no cycle has a negative total weight. A negative-weight cycle makes a shortest path undefined because looping can reduce the route cost without limit; after Floyd–Warshall runs, a negative diagonal distance signals such a cycle. section 9.3

Floyd–Warshall suits dense graphs when exact distances between every pair are needed. Its work is O(V³) regardless of edge count, so repeatedly running a single-source algorithm is more efficient for sparse graphs. section 9.3

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines minimum-weight routes and describes intermediate-vertex updates, negative-edge handling, and negative-cycle detection.
What you can do after
Evaluate/understand when Floyd–Warshall fits dense all-pairs graphs, and diagnose/debug negative cycles by checking for negative diagonal distances.
How it connects
Connects shortest paths to dynamic programming, Floyd–Warshall, Dijkstra’s algorithm, and negative-weight-cycle detection.

Also explained in

Compare how 7 books explain shortest path →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.