Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 24

The authors discuss the problems related to single source shortest paths. For a weighted directed graph $ G = (V,E) $ with weight function $ w: E \rightarrow R $, weight of a path $ p = <v_0,v_1,...,v_k> $ is defined as the sum of the weights of its constituent edges: $ w(p) = \displaystyle\sum\limits_{i=1}^{k} w(v_{i-1},v_i) $. The shortest path weight from $u$ to $v$ is defined as $$ \delta(u,v) = \begin{cases} min \{w(p) : u \overset{p}{\leadsto} v \} & \text{ if there is a path from u to v}, \\
\infty & \text{ otherwise}.
\end{cases} $$ The shortest path from vertex $u$ to vertex $v$ is defined as any path $p$ with weight $ w(p) = \delta(u,v) $.

The authors discuss about different variants of the problem like single destination shortest paths, single-pair shortest path and all-pairs shortest paths. The authors point out that the problem of finding the shortest path has optimal sub-structure property and proves a lemma for it. The authors point out that all the edges need to have non-negative weight for some of the algorithms they are going to discuss. The authors also derive that the shortest path will not have any cycles. The authors then define shortest paths tree.

The authors then define some properties of shortest paths such as

• Triangle inequality property
• Upper-bound property
• No-path property
• Convergence property
• Path-relaxation property
• Predecessor-subgraph property

The authors define conventions of doing arithmetic with infinites and describe that the algorithms assume an adjacency-list representation of graph.

The authors then describe the Bellman Ford algorithm of single source shortest paths and prove its correctness.

The authors then discuss single source shortest paths in directed acyclic graph (DAG). By relaxing the edges of a weighted DAG according to the topological sort of its vertices, shortest paths from a single source can be computed in $ \Theta (V + E) $ time. The authors provide an algorithm based on this observation.

The authors then describe Dijkstra's algorithm for shortest path which solves single source shortest path problem for directed graph $ G = (V,E) $ for the case where all the edge weights are non-negative. The authors prove the correctness of the algorithm and derive that the total running time of the algorithm is $ O((E+V) \lg V) $.

The authors discuss Linear Programming problem where given an $ m \times n $ matrix $A$, an $m$-vector $b$ and an $n$-vector c, we need to find an $n$-vector $x$ that maximizes the objective function $ \displaystyle\sum\limits_{i=1}^n c_i \times x_i$ subject to the $m$ constraints given by $A \times x \le b$.

The authors describe the importance of linear programming problem and show that single-source shortest path, single-pair shortest path and multiflow problems can be reduced to a special case of linear programming problem. The authors describe a variation of this problem as feasibility problem where any $ n $-vector that satisfies $A \times x \le b$ is to be found.

The authors describe system of difference constraints where each row of the linear programming matrix $ A $ contains one 1 and one -1, and all other entries in $A$ are zero. This results in a set of $m$ difference constraints involving $ n $ unknowns where each constraint is of the form
$ x_j - x_i \le b_k $, where $ 1 \le i, j \le n $ and $ 1 \le k \le m $.

The authors then describe constraint graphs and show how the system of difference constraints problem maps to finding single-source shortest path in constraint graph. The $ m \times n $ linear programming matrix $ A $ can be seen as a transpose of an incidence matrix for a graph with $n$ vertices and $m$ edges. Each vertex $ v_i $ in the graph corresponds to one of the $n$ unknown variables $ x_i $ plus there is an additional vertex $ v_0 $. Each of the directed edge in the graph corresponds to one of the $ m $ inequalities such that $ E = \{ (v_i,v_j):x_j - x_i \le b_k \text{ is a constraint } \} \cup \{ (v_0 , v_1), (v_0 , v_2), ... , (v_0 , v_n) \} $ and $ w(v_i , v_j) = b_k $ and $ w(v_0 , v_i) = 0, 1 \le i \le n $.

The authors then describe that Bellman Algorithm can solve the problem in $ O(n^2 + n \times m) $ time. The authors prove all the six properties mentioned above using several lemma and theorems. The authors conclude the chapter with mention of some other algorithms.