CSCE 411 Lecture 20

Lecture Slides

« previous | Friday, October 12, 2012 | next »

Shortest Paths

Weighted Graph (no negative weights)

If all weights are same, BFS would give shortest path.

Algorithm makes use of a priority queue

Dijkstra's Single Source Shortest Path Algorithm

• Assume all edge weights are nonnegative
• Similar to Prim's MST algorithm (greedily choose the lightest edge)

1. Keep an estimate $d_{u}$ of the shortest path distance from $s$ to $u$
2. Use $d$ as the key in a priority queue
3. When $u$ is added to the tree, check each of $u$'s neighbors $v$ to see if $u$ provides $v$ with a cheaper path from $s$: compare $d_{v}$ to $d_{u}+w(u,v)$

def dijkstra_sssp graph, source

  pq = PriorityQueue.new
  graph.each_vertex do |v|
    v.distance = Float::INFINITY
    pq.insert v.distance, v
  end
  source.distance = 0

  until pq.empty?
    u = pq.extract_min
    u.neighbors.each do |v|
      if u.distance + graph.weight(u,v) < v.distance
        v.distance = u.distance + graph.weight(u,v)
        pq.decrease_key(v, v.distance)
        v.parent = u
      end
    end
  end
end

Correctness

Let $T_{i}$ be the tree constructed after the $i$^th iteration of the while loop:

• The nodes in $T_{i}$ are not in $Q$
• The edges in $T_{i}$ are indicated by their parent variables

Claim. The pathi n $T_{i}$ from $s$ to $u$ is a shortest path and has a distance $d_{u}$ for all $u\in T_{i}$

Proof by induction.
Basis: When $i=1$, $s$ is the only node in $T_{1}$ and $d_{s}=0$.

Induction: Assume $T_{i}$ is a correct shortest path tree. We need to show that $T_{i+1}$ is a correct shortest path tree as well.

Let $u$ be the node added in iteration $i$. Let $x=u{\mathtt {.parent}}$. We need to show that the path $P$ in $T_{i+1}$ from $s\to x$ to $u$ is a shortest path, and has distance $d_{u}$.

Let $P'$ be another path from $s$ to $u$. Let $(a,b)$ be the first edge in $P'$ that leaves $T_{i}$.

If $P'_{1}$ is the part before $(a,b)$ and $P'_{2}$ is the part after $(a,b)$, then

${\begin{aligned}w(P')&=w(P'_{1})+w(a,b)+w(P'_{2})\\&\geq w(P'_{1})+w(a,b)\\&\geq w(s\to a\in T_{i})+w(a,b)\quad *\\&\geq w(s\to x\in T_{i})+w(x,u)=w(P)\end{aligned}}$

* $w(s\to a\in T_{1})$ represents the shortest path, and provides a lower bound for $w(P'_{1})$ (any path from $s$ to $a$).

Therefore, $w(P')>w(P)$, and the claim holds by induction on $i$.

Q.E.D.

Running Time

Basic running time: $O(V(T_{ins}+T_{ex})+E\cdot T_{dec})$

using binary heap

$T_{ins}=T_{ex}=T_{dec}=O(\log {V})$

$O(E\log {V})$

using Fibonacci heap

$T_{ins}=O(1)$, $T_{ex}=O(\log {n})$, $T_{dec}=O(1)$

$O(V\log {V}+E)$