Skip to content

24.3 Dijkstra's algorithm

24.3-1

Run Dijkstra's algorithm on the directed graph of Figure 24.2, first using vertex $s$ as the source and then using vertex $z$ as the source. In the style of Figure 24.6, show the $d$ and $\pi$ values and the vertices in set $S$ after each iteration of the while loop.

  • $s$ as the source:

    • $d$ values:

      $$ \begin{array}{ccccc} s & t & x & y & z \\ \hline 0 & 3 & \infty & 5 & \infty \\ 0 & 3 & 9 & 5 & \infty \\ 0 & 3 & 9 & 5 & 11 \\ 0 & 3 & 9 & 5 & 11 \\ 0 & 3 & 9 & 5 & 11 \end{array} $$

    • $\pi$ values:

      $$ \begin{array}{ccccc} s & t & x & y & z \\ \hline \text{NIL} & s & \text{NIL} & \text{NIL} & \text{NIL} \\ \text{NIL} & s & t & s & \text{NIL} \\ \text{NIL} & s & t & s & y \\ \text{NIL} & s & t & s & y \\ \text{NIL} & s & t & s & y \end{array} $$

  • $z$ as the source:

    • $d$ values:

      $$ \begin{array}{ccccc} s & t & x & y & z \\ \hline 3 & \infty & 7 & \infty & 0 \\ 3 & 6 & 7 & 8 & 0 \\ 3 & 6 & 7 & 8 & 0 \\ 3 & 6 & 7 & 8 & 0 \\ 3 & 6 & 7 & 8 & 0 \end{array} $$

    • $\pi$ values:

      $$ \begin{array}{ccccc} s & t & x & y & z \\ \hline z & \text{NIL} & z & \text{NIL} & \text{NIL} \\ z & s & z & s & \text{NIL} \\ z & s & z & s & \text{NIL} \\ z & s & z & s & \text{NIL} \\ z & s & z & s & \text{NIL} \end{array} $$

24.3-2

Give a simple example of a directed graph with negative-weight edges for which Dijkstra's algorithm produces incorrect answers. Why doesn't the proof of Theorem 24.6 go through when negative-weight edges are allowed?

Consider any graph with a negative cycle. $\text{RELAX}$ is called a finite number of times but the distance to any vertex on the cycle is $-\infty$, so Dijkstra's algorithm cannot possibly be correct here. The proof of theorem 24.6 doesn't go through because we can no longer guarantee that

$$\delta(s, y) \le \delta(s, u).$$

24.3-3

Suppose we change line 4 of Dijkstra's algorithm to the following.

1
 4  while |Q| > 1

This change causes the while loop to execute $|V| - 1$ times instead of $|V|$ times. Is this proposed algorithm correct?

Yes, the algorithm still works. Let $u$ be the leftover vertex that does not get extracted from the priority queue $Q$. If $u$ is not reachable from $s$, then $u.d = \delta(s, u) = \infty$. If $u$ is reachable from $s$, then there is a shortest path $p = s \leadsto x \to u$. When the vertex $x$ was extracted, $x.d = \delta(s, x)$ and then the edge $(x, u)$ was relaxed; thus, $u.d = \delta(s, u)$.

24.3-4

Professor Gaedel has written a program that he claims implements Dijkstra's algorithm. The program produces $v.d$ and $v.\pi$ for each vertex $v \in V$. Give an $O(V + E)$-time algorithm to check the output of the professor's program. It should determine whether the $d$ and $\pi$ attributes match those of some shortest-paths tree. You may assume that all edge weights are nonnegative.

  1. Verify that $s.d = 0$ and $s.\pi = \text{NIL}$
  2. Verify that $v.d = v.\pi.d + w(v.\pi, v)$ for all $v \notin s$.
  3. Verify that $v.d = \infty$ if and only if $v.\pi = \text{NIL}$ for all $v \notin s$.
  4. If any of the above verification tests fail, declare the output to be incorrect. Otherwise, run one pass of Bellman-Ford, i.e., relax each edge $(u, v) \in E$ one time. If any values of $v.d$ change, then declare the output to be incorrect; otherwise, declare the output to be correct.

24.3-5

Professor Newman thinks that he has worked out a simpler proof of correctness for Dijkstra's algorithm. He claims that Dijkstra's algorithm relaxes the edges of every shortest path in the graph in the order in which they appear on the path, and therefore the path-relaxation property applies to every vertex reachable from the source. Show that the professor is mistaken by constructing a directed graph for which Dijkstra's algorithm could relax the edges of a shortest path out of order.

Let the graph have vertices $s$, $x$, $y$, $z$ and edges $(s, x)$, $(x, y)$, $(y, z)$, $(s, y)$, and let every edge have weight $0$. Dijkstra's algorithm could relax edges in the order $(s, y)$, $(s, x)$, $(y, z)$, $(x, y)$. The graph has two shortest paths from $s$ to $z: \langle s, x, y, z \rangle$ and $\langle s, y, z \rangle$, both with weight $0$. The edges on the shortest path $\langle s, x, y, z \rangle$ are relaxed out of order, because $(x, y)$ is relaxed after $(y, z)$.

24.3-6

We are given a directed graph $G = (V, E)$ on which each edge $(u, v) \in E$ has an associated value $r(u, v)$, which is a real number in the range $0 \le r(u, v) \le 1$ that represents the reliability of a communication channel from vertex $u$ to vertex $v$. We interpret $r(u, v)$ as the probability that the channel from $u$ to $v$ will not fail, and we assume that these probabilities are independent. Give an efficient algorithm to find the most reliable path between two given vertices.

To find the most reliable path between $s$ and $t$, run Dijkstra's algorithm with edge weights $w(u, v) = -\lg r(u, v)$ to find shortest paths from $s$ in $O(E + V\lg V)$ time. The most reliable path is the shortest path from $s$ to $t$, and that path's reliability is the product of the reliabilities of its edges.

Here's why this method works. Because the probabilities are independent, the probability that a path will not fail is the product of the probabilities that its edges will not fail. We want to find a path $s \overset{p}{\leadsto} t$ such that $\prod_{(u, v) \in p} r(u, v)$ is maximized. This is equivalent to maximizing $\lg(\prod_{(u, v) \in p} r(u, v)) = \sum_{(u, v) \in p} \lg r(u, v)$, which is in turn equivalent to minimizing $\sum_{(u, v) \in p} -\lg r(u, v)$. (Note: $r(u, v)$ can be $0$, and $\lg 0$ is undefined. So in this algorithm, define $\lg 0 = -\infty$.) Thus if we assign weights $w(u, v) = -\lg r(u, v)$, we have a shortest-path problem.

Since $\lg 1 = 0$, $\lg x < 0$ for $0 < x < 1$, and we have defined $\lg 0 = -\infty$, all the weights $w$ are nonnegative, and we can use Dijkstra's algorithm to find the shortest paths from $s$ in $O(E + V\lg V)$ time.

Alternative solution

You can also work with the original probabilities by running a modified version of Dijkstra's algorithm that maximizes the product of reliabilities along a path instead of minimizing the sum of weights along a path.

In Dijkstra's algorithm, use the reliabilities as edge weights and substitute

  • max (and $\text{EXTRACT-MAX}$) for min (and $\text{EXTRACT-MIN}$) in relaxation and the queue,
  • $\cdot$ for $+$ in relaxation,
  • $1$ (identity for $\cdot$) for $0$ (identity for $+$) and $-\infty$ (identity for min) for $\infty$ (identity for max).

For example, we would use the following instead of the usual $\text{RELAX}$ procedure:

1
2
3
4
RELAX-RELIABILITY(u, v, r)
    if v.d < u.d * r(u, v)
        v.d = u.d * r(u, v)
        v.π = u

This algorithm is isomorphic to the one above: it performs the same operations except that it is working with the original probabilities instead of the transformed ones.

24.3-7

Let $G = (V, E)$ be a weighted, directed graph with positive weight function $w: E \rightarrow \{1, 2, \ldots, W\}$ for some positive integer $W$, and assume that no two vertices have the same shortest-path weights from source vertex $s$. Now suppose that we define an unweighted, directed graph $G' = (V \cup V', E')$ by replacing each edge $(u, v) \in E$ with $w(u, v)$ unit-weight edges in series. How many vertices does $G'$ have? Now suppose that we run a breadth-first search on $G'$. Show that the order in which the breadth-first search of $G'$ colors vertices in $V$ black is the same as the order in which Dijkstra's algorithm extracts the vertices of $V$ from the priority queue when it runs on $G$.

$V + \sum_{(u, v) \in E} w(u, v) - E$.

24.3-8

Let $G = (V, E)$ be a weighted, directed graph with nonnegative weight function $w: E \rightarrow \{0, 1, \ldots, W\}$ for some nonnegative integer $W$. Modify Dijkstra's algorithm to compute the shortest paths from a given source vertex s in $O(WV + E)$ time.

Observe that if a shortest-path estimate is not $\infty$, then it's at most $(|V| - 1)W$. Why? In order to have $v.d < 1$, we must have relaxed an edge $(u, v)$ with $u.d < \infty$. By induction, we can show that if we relax $(u, v)$, then $v.d$ is at most the number of edges on a path from $s$ to $v$ times the maximum edge weight. Since any acyclic path has at most $|V| - 1$ edges and the maximum edge weight is $W$, we see that $v.d \le (|V| - 1)W$. Note also that $v.d$ must also be an integer, unless it is $\infty$.

We also observe that in Dijkstra's algorithm, the values returned by the $\text{EXTRACT-MIN}$ calls are monotonically increasing over time. Why? After we do our initial $|V|$ $\text{INSERT}$ operations, we never do another. The only other way that a key value can change is by a $\text{DECREASE-KEY}$ operation. Since edge weights are nonnegative, when we relax an edge $(u, v)$, we have that $u.d \le v.d$. Since $u$ is the minimum vertex that we just extracted, we know that any other vertex we extract later has a key value that is at least $u.d$.

When keys are known to be integers in the range $0$ to $k$ and the key values extracted are monotonically increasing over time, we can implement a min-priority queue so that any sequence of $m$ $\text{INSERT}$, $\text{EXTRACT-MIN}$, and $\text{DECREASE-KEY}$ operations takes $O(m + k)$ time. Here's how. We use an array, say $A[0..k]$, where $A[j]$ is a linked list of each element whose key is $j$. Think of $A[j]$ as a bucket for all elements with key $j$. We implement each bucket by a circular, doubly linked list with a sentinel, so that we can insert into or delete from each bucket in $O(1)$ time. We perform the min-priority queue operations as follows:

  • $\text{INSERT}$: To insert an element with key $j$, just insert it into the linked list in $A[j]$. Time: $O(1)$ per $\text{INSERT}$.
  • $\text{EXTRACT-MIN}$: We maintain an index $min$ of the value of the smallest key extracted. Initially, $min$ is $0$. To find the smallest key, look in $A[min]$ and, if this list is nonempty, use any element in it, removing the element from the list and returning it to the caller. Otherwise, we rely on the monotonicity property and increment $min$ until we either find a list $A[min]$ that is nonempty (using any element in $A[min]$ as before) or we run off the end of the array $A$ (in which case the min-priority queue is empty).

    Since there are at most $m$ $\text{INSERT}$ operations, there are at most $m$ elements in the min-priority queue. We increment $min$ at most $k$ times, and we remove and return some element at most $m$ times. Thus, the total time over all $\text{EXTRACT-MIN}$ operations is $O(m + k)$.

  • $\text{DECREASE-KEY}$: To decrease the key of an element from $j$ to $i$, first check whether $i \le j$, flagging an error if not. Otherwise, we remove the element from its list $A[j]$ in $O(1)$ time and insert it into the list $A[i]$ in $O(1)$ time. Time: $O(1)$ per $\text{DECREASE-KEY}$.

    To apply this kind of min-priority queue to Dijkstra's algorithm, we need to let $k = (|V| - 1)W$, and we also need a separate list for keys with value $\infty$. The number of operations $m$ is $O(V + E)$ (since there are $|V|$ $\text{INSERT}$ and $|V|$ $\text{EXTRACT-MIN}$ operations and at most $|E|$ $\text{DECREASE-KEY}$ operations), and so the total time is $O(V + E + VW) = O(VW + E)$.

24.3-9

Modify your algorithm from Exercise 24.3-8 to run in $O((V + E) \lg W)$ time. ($\textit{Hint:}$ How many distinct shortest-path estimates can there be in $V - S$ at any point in time?)

First, observe that at any time, there are at most $W + 2$ distinct key values in the priority queue. Why? A key value is either $1$ or it is not. Consider what happens whenever a key value $v.d$ becomes finite. It must have occurred due to the relaxation of an edge $(u, v)$. At that time, $u$ was being placed into $S$, and $u.d \le y.d$ for all vertices $y \in V - S$. After relaxing edge $(u, v)$, we have $v.d \le u.d + W$. Since any other vertex $y \in V - S$ with $y.d < \infty$ also had its estimate changed by a relaxation of some edge $x$ with $x.d \le u.d$, we must have $y.d \le x.d + W \le u.d + W$. Thus, at the time that we are relaxing edges from a vertex $u$, we must have, for all vertices $v \in V - S$, that $u.d \le v.d \le u.d + W$ or $v.d = \infty$. Since shortest-path estimates are integer values (except for $\infty$), at any given moment we have at most $W + 2$ different ones: $u.d$, $u.d + 1$, $u.d + 2$, $\ldots$, $u.d + W$ and $\infty$.

Therefore, we can maintain the min-priorty queue as a binary min-heap in which each node points to a doubly linked list of all vertices with a given key value. There are at most $W + 2$ nodes in the heap, and so $\text{EXTRACT-MIN}$ runs in $O(\lg W)$ time. To perform $\text{DECREASE-KEY}$, we need to be able to find the heap node corresponding to a given key in $O(\lg W)$ time. We can do so in $O(1)$ time as follows. First, keep a pointer $inf$ to the node containing all the $\infty$ keys. Second, maintain an array $loc[0..W]$, where $loc[i]$ points to the unique heap entry whose key value is congruent to $i(\mod(W + 1))$. As keys move around in the heap, we can update this array in $O(1)$ time per movement.

Alternatively, instead of using a binary min-heap, we could use a red-black tree. Now $\text{INSERT}$, $\text{DELETE}$, $\text{MINIMUM}$, and $\text{SEARCH}$—from which we can construct the priority-queue operations—each run in $O(\lg W)$ time.

24.3-10

Suppose that we are given a weighted, directed graph $G = (V, E)$ in which edges that leave the source vertex $s$ may have negative weights, all other edge weights are nonnegative, and there are no negative-weight cycles. Argue that Dijkstra's algorithm correctly finds shortest paths from $s$ in this graph.

The proof of correctness, Theorem 24.6, goes through exactly as stated in the text. The key fact was that $\delta(s, y) \le \delta(s, u)$. It is claimed that this holds because there are no negative edge weights, but in fact that is stronger than is needed. This always holds if $y$ occurs on a shortest path from $s$ to $u$ and $y \ne s$ because all edges on the path from $y$ to $u$ have nonnegative weight. If any had negative weight, this would imply that we had "gone back" to an edge incident with $s$, which implies that a cycle is involved in the path, which would only be the case if it were a negative-weight cycle. However, these are still forbidden.