- Shortest path weight from Vertex a to b: δ(a,b)
- infinity if b is unreachable from a, else min(PW(p))
Algorithms
initSSSP(s) // initialisation
for each v in V
D[v] = infinity // or 1B
p[v] = -1 // NULL
D[s] = 0 // what we know so far
relax(u, v, w(u,v)) //relaxation operation
if D[v] > D[u] + w(u,v) // SP can be shortened
D[v] = D[u] + w(u,v) // relax this edge
p[v] = u // rmb/update the predecessor
// if necessary update some data structureSSSP - Terminating Condition
- algo has solved SSSP when for all edges (u,v), D[v] ≤ D[u] + w(u,v) [no edge can be relaxed further]
initSSSP(s)
repeat // main loop
select edge (u,v) in E **in arbitrary manner**
relax(u, v, w(u,v))
until all edges have D[v] <= D[u] + w(u,v)
// can be very slow... BF algo does relaxations
// in a better order!Graph representations: choose Adj List for BFS/Bellman-Ford/Dijkstra’s, Adj Matrix for dense graphs → L12 Graphs
For All-Pairs Shortest Paths: → L17 APSP
| Algorithm | Usefulness | Description |
|---|---|---|
| Modified BFS O(V+E) | Unweighted graph / constant weight edges → find least number of edges traversed from s to others will not consider a longer path with shorter weights | - graph can be directed / undirected - data structure: adj list - replace visited array with distance array D - increase distance by 1 when moving to next vertex |
| Bellman Ford’s O(VE) | 1. general weighted graph 2. detect negative weight cycle | - graph can be directed / undirected - data structure: adj list / edge list - to detect -ve weight cycle, run the algo an extra time aft executing it for V-1 times → if any edge relaxes, -ve weight cycle exists Key idea: 1. initialise 2. perform next step V-1 times: - for every edge, if edge can be relaxed, relax and set p[v] = u |
Bellman-Ford
- worst case complete graph: E = V^2 → O(V^3)
Modified BFS
// initialisation
for all v in V
D[v] = INF
p[v] = -1
Q = {s} // start from s
D[s] = 0
while Q is not empty // main
u = Q.dequeue()
// order of neighbour
for all v adjacent to u
// influences BFS
if D[v] = INF
// visitation sequence
D[v] = D[u] + 1
p[v] = u
Q.enqueue(v)- Optimise
- stop when no more relaxation after a pass (can flag out)
- performance on small graphs:
- without -ve weight cycle = OK, in O(VE)
- with -ve weight cycle = terminates in O(VE)
- some -ve edges, no -ve cycle = OK
Special Cases
| Tree O(V) | - BFS / DFS → L13 Graph Traversal - every path in tree is a shortest path, just traverse all nodes → spanning tree - if neighbour is predecessor, don’t visit it - since O(V+E) = O(V + V-1) = O(V) |
|---|---|
| Unweighted O(V+E) | BFS only |
| DAG O(V+E) + O(E) | - Toposort → L13 Graph Traversal , One pass Bellman Ford’s - can do an ordering of the vertices - topological sort (kahn’s algo) - modify BF by replacing outermost V-1 loop to just one pass → only run the relaxation across all edges once in topological order |
| No negative weight edge O((V+E)logV) | Dijkstra’s - can use Bellman Ford’s but runs in O(VE) → for a reasonably sized weighted graph with V → E=O(V^2) in a complete simple graph, BF is really slow: O(V^3) |
| No negative weight cycle O((V+E)logV) = O(E log E) | Modified Dijkstra’s Formal assumption: the graph has no negative weight cycle (but can have negative weight edges) |
| General case: weighted graph O(VE) | Bellman Ford’s |
| Shortest path cost of multiple sources to same destination T | - Flip all edges in the graphs (if it is directed) & perform SSSP algorithm from T - the shortest path from vertex v to T D[v→T] is D[T→v] in our transformed graph undirected connected weighted graph, non-negative edge weights: - run dijkstra’s from T to get the SPs from T to all other vertices - since the graph is undirected, reversing these paths will give the SPs from other vertices to T - *O((V+E)logV) time |
More Algorithms
| Algorithm | Usefulness | Description |
|---|---|---|
| Dijkstra’s O((V+E)logV) | Graphs with no negative edge weight Uses min-heap (Priority Queue) → L8 Heap | - Each vertex is only processed once Key Ideas: - maintain a set Solved of vertices whose final shortest path weights have been determined, initially Solved = {s}, source vertex s only - repeatedly select vertex u in {V - Solved} with the min shortest path estimate D[u], add u to Solved, relax all edges out of u - greedy algorithm → select best so far - Vertices added to Solved in non-decreasing SP costs * can detect if graph contains -ve edge weight: → reports true when it tries to update shortest dist of a vertex in PQ but is unable to find (vertex alr in solved) → cannot be used to differentiate between -ve edge weight and cycle |
| Modified Dijkstra’s ”lazy data structure” strat O(E log E) = O((V+E)logV) except faster when E<O(V) (disconnected) then O(E log E) < O(V log V) | Graphs with no negative weight cycle | - Each vertex can be processed multiple times (due to presence of negative edge weight) - runs faster than Bellman Ford’s - can be trapped if there is -ve weight cycle → use BF instead if high probability of -ve weight cycle Key idea: - Enqueue (0,s) into a normal PQ - Remove vertex u with minimum d from PQ [min shortest path estimate so far] - if D[u] == d, relax all edges out of u. if an edge (u,v) is relaxed, update D[v] & enqueue new (d,v) into PQ - else if d > D[u], discard this inferior (d,u) pair |
Dijkstra’s
relax outgoing edges from nodes close to source then relax from nodes further away
- Min PQ: store the shortest path estimate for a vertex v as IntegerPair(d,v) in the PQ, d = D[v] (current shortest path estimate)
- Enqueue all vertices as Pair(INF, v), except source (0,s) into PQ
- Main loop: keep removing vertex u with minimum d from PQ, add u into Solved, relax all outgoing edges
- update D[v] and (d,v) in PQ once edge(u,v) is relaxed
- use bBST to implement PQ
Modified Dijkstra’s
initSSSP(s)
// store pair of (dist[u], u)
PQ.enqueue((0,s))
// order: increasing dist[u]
while PQ is not empty
(d,u) = PQ.dequeue()
if d == D[u] // impt check, lazy
for each vertex v adjacent to u
// can relax
if D[v] > D[u] + w(u,v)
D[v] = D[u] + w(u,v) // rlx
PQ.enqueue(D[v], v)
// re-enqueue this