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
- \(\delta(u, v)\) - minimum with path from \(u\) to \(v\)
- \(\infty\) - if no path exists
shortest path is any path \(p\) with weight \(w(p) = \delta(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 \(\delta(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, \(\pi\)
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.\pi\) 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 \(\delta(s, v) \leq \delta(s, u) + w(u, v)\)
Upper-bound property \(v.d \geq \delta(s,v)\) always, and once \(v.d\) achieves \(\delta(s, v)\) it never changes
No-path property when no path from \(s\) to \(v\) exists \(v.d = \delta(s, v) = \infty\)
Convergence property If \(s \leadsto u \rightarrow v\) is a shortest path in \(G\) for some \(u, v \in V\), and if \(u.d = \delta(s, u)\) at any time prior to relaxing edge \((u, v)\), then \(v.d = \delta(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=\delta(s, v_k)\)
Predecessor subgraph property once \(v.d = \delta(s,v)\) for all \(v \in V\), the predecessor subgraph is a shortest-paths tree rooted at \(s\)