# Shortest-Paths Problem > Alternatively, refer to [[all-pair-shortest-path]]. - By [[bfs|breadth-first search]], $\delta(s, v) = v.d$, construct one of the paths by traverse $(v.\pi, v)$ and so on. (for unweighted graphs) - Optimal substructure: any subpath $v_i \overset{p_{ij}}\leadsto v_j$ is also a shortest path from $v_i$ to $v_j$. - _Predecessor subgraph_: $G_\pi = (V_\pi, E_\pi)$, 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.\pi$. - 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|Bellman-Ford Algorithm]] $O(V^2 + VE)$ - For a dag, simply perform [[topological-sort]], and relax the edges in the adjacency list of each vertex. $O(V + E)$ - [[dijkstra|Dijkstra's Algorithm]]