Single Source Shortest Path

Summarized notes on Introduction to Algorithms, Chapter 24

shortest-path problem - given an weighted, directed graph
→ goal is to solve it efficiently
weight of path is is the sum of weights of its constituent edges
shortest-path weight
- $δ (u, v)$ - minimum with path from $u$ to $v$
- $\infty$ - if no path exists
shortest path is any path $p$ with weight $w (p) = δ (u, v)$

Single-source shortest path find shortest path from source vertex $s$ to each vertex $v \in V$

Variants of SSSP:

Graphs may contain negative weight edges

when no negative weight cycle is reachable from $s$ , weights remain well defined
if graph contains negative weight cycle reachable from $s$ , shortest-path weights are not well defined
If there is a negative weight cycle $δ (u, v) = - \infty$

Shortest path has no cycles (negative or positive weight), i.e. it is a simple path
→ such path has at most $V$ vertices and $V - 1$ edges

Representing shortest paths:

similar to breath-first trees: maintain predecessor attribute, $π$
shortest-paths tree is directed subgraph $G^{'} = (V^{'}, E^{'})$
- $V^{'}$ vertices reachable from $s$
- $G^{'}$ rooted tree with $s$ being the root
- path from $s$ to $v$ in $G^{'}$ is shortest path from $s$ to $v$ in $G$

Relaxation

each vertex maintains attribute $v . d$ shortest-path estimate → upper bound on the weight of shortest path from $s$ to $v$
when relaxing an edge, test if shortest path found so far can be improved, and if yes update $v . π$ and $v . d$
relaxation is the only means by which shortest-path estimates and predecessors change

Pseud code implementation

These helper functions are needed to implement SSSP algorithms

Initialize-single-source(G, s)
    for each vertex v in G.V
        v.d = infty
        v.pi = NIL
    s.d = 0

Relax(u, v, w)
    if v.d > u.d + w(u, v)
        v.d = u.d + w(u, v)
        v.pi = u

Triangle inequality $δ (s, v) \leq δ (s, u) + w (u, v)$
Upper-bound property $v . d \geq δ (s, v)$ always, and once $v . d$ achieves $δ (s, v)$ it never changes
No-path property when no path from $s$ to $v$ exists $v . d = δ (s, v) = \infty$
Convergence property If $s ⇝ u \to v$ is a shortest path in $G$ for some $u, v \in V$ , and if $u . d = δ (s, u)$ at any time prior to relaxing edge $(u, v)$ , then $v . d = δ (s, v)$ at all times afterward
Path-relaxation property consider path from $s = v_{0}$ to $v_{k}$ then relax edges in order then $v_{k} . d = δ (s, v_{k})$
Predecessor subgraph property once $v . d = δ (s, v)$ for all $v \in V$ , the predecessor subgraph is a shortest-paths tree rooted at $s$