Card 11/ 11
Recap: Shortest Paths
Breadth-first for no weights, Dijkstra for non-negative, Bellman-Ford for negative, Floyd-Warshall for every pair.
Shortest Paths covered four ways to find the cheapest route in a graph, and the three questions that choose between them: are there weights, can any be negative, and are all pairs needed. The table names each idea and the card that holds it.
| The idea | Where |
|---|---|
| Weights, relaxation, negative cycles, and the decision between four algorithms | Shortest Paths: Choosing an Algorithm by Weights and Pairs |
| Settle the closest unsettled vertex; distances, settled set, parents and queue are four things | Dijkstra's Algorithm: Settling the Closest Vertex Next |
| A heap with lazy deletion, or a scan in O(V²) | Dijkstra's Algorithm in Python, Java and TypeScript |
| V − 1 passes over every edge, and one more to find a negative cycle | Bellman-Ford: Relaxing Every Edge V − 1 Times |
| An edge list, an early stop and an overflow guard | Bellman-Ford in Python, Java and TypeScript |
| After round k, routes with stops up to k; next hops rebuild a path | Floyd-Warshall: Allowing One More Stop Each Round |
| Three loops with k outside | Floyd-Warshall in Python, Java and TypeScript |
| One greedy algorithm and two dynamic programmes, by what they accept and cost | Dijkstra vs Bellman-Ford vs Floyd-Warshall |
| A negative edge into a settled vertex gives a wrong distance with no error | Running Dijkstra's Algorithm on a Negative Edge |
| Tracing fares, and seeing a rebate as a negative edge | Practice: Planning the Cheapest Ferry Crossings |
Every algorithm in the topic relaxes edges; what differs is the order. Dijkstra's algorithm relaxes from the closest vertex and commits, which is fast and needs every weight to be 0 or more. Bellman-Ford relaxes everything again and again until no path can have more edges, and Floyd-Warshall admits one more stop per round. On the topic's graph all of them agreed: A 0, B 2, C 5, D 7, E 8, along A B C D E, a path of four edges where the fewest edges would cost 13.
When Every edge costs the same, or the graph has no weights
, chooseWhen Paths from one source are needed, and no weight is negative
, chooseWhen Paths from one source are needed, some weights are negative, or a negative cycle must be detected
, chooseWhen The distance between every pair is needed, and the graph has a few hundred vertices at most
, choose
Otherwise For every pair on a larger graph with no negative weights, run Dijkstra's algorithm once from each vertex.
A shortest-path tree reaches every vertex from one source as cheaply as possible. Connecting every vertex to every other with the least total weight of edges is a different question with a different answer, and Minimum Spanning Trees, the next topic, takes it up.
← → move through sections and cards