Part I
Two algorithms:
- Dijkstra $O(VlgV + E)$ assumes non-negative edge weights
- Bellman Ford $O(VE)$ is a general algorithm
Weighted graphs
Single Source Shortest Paths:
Given $G = (V, E)$, $w$ and a source vertex $S$, find $δ(S, V)$ [and the best path] from $S$ to each $v∈V$.
Data structures:1
2
3
4
5d[v] = value inside circle
= 0, if v = s
= ∞, otherwise ⇐ initially
d[v] = δ (s,v) ⇐ at end
d[v] \le δ (s,v) at all times
$d[v]$ decreases as we find better paths to v
$Π[v]$ = predecessor on best path to $v$, $Π[s] = NIL$
Negative-Weight Edges:
If negative weight edges are present, s.p. algorithm should find negative weight cycles (e.g., Bellman Ford)
General approach
General structure of S.P. Algorithms (no negative cycles):
Optimal substructure
Theorem: Subpaths of shortest paths are shortest paths
Let $p = < v_0, v_1, . . . v_k >$ be a shortest path
Let $p_{ij} = < v_i, v_{i+1}, . . . v_j >$ $0 ≤ i ≤ j ≤ k$
Then $p_{ij}$ is a shortest path.
Part II
DAG
- Topologically sort the DAG. Path from u to v implies that u is before v in the linear ordering.
- One pass over vertices in topologically sorted order relaxing each edge that leaves each vertex.
Note: Can’t have negative cycles because there are no cycles!
Dijkstra’s Algorithm
- The idea is to maintain two sets
- one set contains vertices included in existing shortest path
- another set includes vertices not yet included.
- At every step of the algorithm, find a vertex
- which is in the set with not included vertex and
- has a minimum distance from the source.
- update the distance of the shorted path set
For each edge $(u, v) \in E$, assume $w(u, v) ≥ 0$, maintain a set S of vertices whose final shortest path weights have been determined. Repeatedly select $u \in V − S$ with minimum shortest path estimate, add u to S, relax all edges out of u.
Pseudo-code1
2
3
4
5
6
7
8
9Dijkstra (G, W, s) //uses priority queue Q
Initialize (G, s)
S ← φ
Q ← V[G] //Insert into Q
while Q = φ
do u ← EXTRACT-MIN(Q) //deletes u from Q
S = S ∪ {u}
for each vertex v $\in$ Adj[u]
do RELAX (u, v, w) ← this is an implicit DECREASE KEY operation
Strategy: Dijkstra is a greedy algorithm: choose closest vertex in V − S to add to set S.
Correctness: We know relaxation is safe. The key observation is that each time a vertex u is added to set S, we have $d[u] = δ(s, u)$.
Dijkstra Complexity
$Θ(v)$ inserts into priority queue
$Θ(v)$ EXTRACT_MIN operations
$Θ(E)$ DECREASE_KEY operations
Array impl:
- Θ(v) time for extra min
- Θ(1) for decrease key
Total: Θ(V.V + E.1) = Θ(V^2 + E) = Θ(V^2)
Binary min-heap:
- Θ(lgV) for extract min
- Θ(lgV) for decrease key
Total: Θ(VlgV + ElgV )
Fibonacci heap:
- Θ(lgV ) for extract min
- Θ(1) for decrease key
- amortized cost
Total: Θ(VlgV + E)