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{.}\mathtt{p}\mathtt{a}\mathtt{r}\mathtt{e}\mathtt{n}\mathtt{t}$. 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^{\prime }$ be another path from $s$ to $u$. Let $(a,b)$ be the first edge in $P^{\prime }$ that leaves $T_i$.

If $P{\text{'}}_1$ is the part before $(a,b)$ and $P{\text{'}}_2$ is the part after $(a,b)$, then

$\begin{array}{rl}w(P^{\prime })& =w(P{\text{'}}_1)+w(a,b)+w(P{\text{'}}_2)\\ & \ge w(P{\text{'}}_1)+w(a,b)\\ & \ge w(s\to a\in T_i)+w(a,b)*\\ & \ge w(s\to x\in T_i)+w(x,u)=w(P)\end{array}$

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

Therefore,

$w(P^{\prime })>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)$