Shortest paths¶
Part 2 · Trees and paths · Chapter 3 · Lecture notes, volume 2 (PDF) · Exercises: Shortest paths · App: Shortest paths: Dijkstra, Bellman–Ford, acyclic graphs
-
3.1 Shortest path problems
Optimality of subpaths
-
3.2 Optimality conditions and potentials
-
3.3 The linear programming formulation
The single-source model
-
3.4 Shortest paths in acyclic graphs
-
3.5 The Bellman–Ford algorithm
-
3.6 Dijkstra's algorithm
Dijkstra's algorithm on the reference graph · Negative lengths
Prerequisites
-
From Chapter 1 «Graphs»: directed walks, paths and cycles, the node–arc incidence matrix, trees and the reference graph.
-
From the module Linear Programming, Chapter 9 «Duality theory»: the dual of an LP model and the weak duality theorem.
Objectives
At the end of this chapter you will be able to:
-
state the \(s\)–\(t\) and the single-source shortest path problems, and recognize when a negative cycle makes them ill-posed;
-
use the optimality of subpaths, Bellman's equations and the shortest path tree;
-
write the LP model of a shortest path as a unit flow, write its dual with the potentials \(\pi_i\), and use feasible potentials as a certificate of optimality;
-
run the algorithm for acyclic graphs, the Bellman–Ford algorithm (with the detection of a negative cycle) and Dijkstra's algorithm, prove their correctness and give their running time.
Next: 3.1 Shortest path problems
Exercises on this chapter: Shortest paths
In the interactive lab: Shortest paths: Dijkstra, Bellman–Ford, acyclic graphs.