Single‐Source Shortest Path - rFronteddu/general_wiki GitHub Wiki
Algorithm Comparison Summary
| Algorithm | Graph Type | Negative Weights | Time Complexity | Core Idea |
|---|---|---|---|---|
| Bellman-Ford | Any | Yes | O(V · E) | Relax all edges V−1 times |
| Dijkstra | No negative weights | No | O((V + E) log V) | Greedy with priority queue |
| SSSP in DAG | DAG only | Yes | O(V + E) | Topological sort + relax in order |
Problem Definition
Given a weighted, directed graph G = (V, E) with a weight function w: E→R that maps edges to real numbers, the goal is to find the shortest path from a source vertex s to all other vertices. The weight of a path p = ${v_0, v_1,\ldots,v_k}$ is defined as the sum of the weights of its edges:
$$ w(p) = \sum_{i=1}^{k} w(v_{i-1}, v_i) $$
The shortest path weight $\delta(u,v)$ from u to v is;
$$ \delta(u,v) = min(w(p) : \text{u → v in p) or ∞ if no path exists}) $$
Example
A road map between cities like Phoenix and Indianapolis can be modeled as a graph:
- Vertices: Intersections
- Edges: Road segments between intersections
- Edge Weights: Distances, travel times, or other metrics.
Algorithm Variants
- Single-Destination Shortest-Paths: Find the s-p from every vertex to a single destination vertex t. This can be reduced to SSSP by reversing the direction of the graph's edges.
- Single-Pair Shortest-Path: Find the s-p between two specific vertices u and v. Solving SSSP for source u also solves this.
- All-Pairs Shortest-Paths: Find the shortest path between every pair of vertices. This can be done by running the SSSP algorithm from each vertex, though there are faster methods.
Optimal Substructure
Shortest path algorithms rely on the optimal substructure property, meaning that any sub-path of a shortest path is also a shortest path. This property is crucial for greedy algorithms like Dijkstra's and dynamic programming algorithms like Bellman-Ford.
Negative-Weight Edges and Cycles:
- Negative Weights: As long as there are no negative-weight cycles, the shortest path is well defined, even if some edge weights are negative.
- Cycles: Shortest paths can be assumed to be simple (i.e., no cycles), and can contain at most |V| - 1 edges.
Representation of Shortest Paths:
Shortest paths are represented similarly to breadth-first search (BFS) trees, where each vertex v has a predecessor v.p, forming a shortest-path tree rooted at the source s.
Relaxation Process:
The relaxation process updates the shortest path estimate v.d. for a vertex v by checking if it can be improved via another vertex u:
RELAX(u,v,w) if v.d > u.d + w(u,v) => v.d = u.d + w(u,v), v.p=u
INIT_SINGLE_SOURCE(G,s)
for v in G.V
v.d = max
v.p = nil
s.d = 0
- Dijkstra's algorithm relaxes each edge once.
- Bellman-Ford algorithm relaxes each edge |V|-1 times and can handle negative weights.
Properties of shortest paths and relaxation
- Triangle Inequality: $\delta(s,u)\leq\delta(s,u)+w(u,v)$
- Upper Bound Property: $v.d\geq \delta(s,v)$, and once $v.d = \delta(s,v)$ it remains unchanged.
- No path property: If no path exists from s to v, then $v.d = \delta(s,v)$ = ∞
- Convergence Property: Once $u.d = \delta(s,u)$, $v.d = \delta(s,v)$ after relaxing (u,v).
- Path Relaxation Property: After relaxing all edges in a shortest path from s to $v_k$, $v_k$.d = $\delta(s,v_k)$
- Predecessor-Subgraph Property: When $v.d = \delta(s,v)$, the predecessor subgraph forms a shortest-path tree.