Shortest-Paths Problem

Alternatively, refer to all-pair-shortest-path.

By breadth-first search, $δ (s, v) = v . d$ , construct one of the paths by traverse $(v . π, v)$ and so on. (for unweighted graphs)
Optimal substructure: any subpath $v_{i} ⇝ p_{ij} v_{j}$ is also a shortest path from $v_{i}$ to $v_{j}$ .
Predecessor subgraph: $G_{π} = (V_{π}, E_{π})$ , and shortest-paths tree
Relaxation technique
- Maintains attribute $v . d$ which is an upper bound on the weight of a shortest path from $s$ to $v$ , i.e. shortest-path estimate.
- Test whether going through $u$ improves shortest path to $v$ found so far, if so update $v . d$ and $v . π$ .
- Different algorithms relaxes a vertex different times

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

Algorithms
- Bellman-Ford Algorithm $O (V^{2} + V E)$
- For a dag, simply perform topological-sort, and relax the edges in the adjacency list of each vertex. $O (V + E)$
- Dijkstra’s Algorithm

My Vault