# 25.3 Johnson's algorithm for sparse graphs

## 25.3-1

Use Johnson's algorithm to find the shortest paths between all pairs of vertices in the graph of Figure 25.2. Show the values of $h$ and $\hat w$ computed by the algorithm.

$$\begin{array}{c|c} v & h(v) \\ \hline 1 & -5 \\ 2 & -3 \\ 3 & 0 \\ 4 & -1 \\ 5 & -6 \\ 6 & -8 \end{array}$$

$$\begin{array}{ccc|ccc} u & v & \hat w(u, v) & u & v & \hat w(u, v) \\ \hline 1 & 2 & \text{NIL} & 4 & 1 & 0 \\ 1 & 3 & \text{NIL} & 4 & 2 & \text{NIL} \\ 1 & 4 & \text{NIL} & 4 & 3 & \text{NIL} \\ 1 & 5 & 0 & 4 & 5 & 8 \\ 1 & 6 & \text{NIL} & 4 & 6 & \text{NIL} \\ 2 & 1 & 3 & 5 & 1 & \text{NIL} \\ 2 & 3 & \text{NIL} & 5 & 2 & 4 \\ 2 & 4 & 0 & 5 & 3 & \text{NIL} \\ 2 & 5 & \text{NIL} & 5 & 4 & \text{NIL} \\ 2 & 6 & \text{NIL} & 5 & 6 & \text{NIL} \\ 3 & 1 & \text{NIL} & 6 & 1 & \text{NIL} \\ 3 & 2 & 5 & 6 & 2 & 0 \\ 3 & 4 & \text{NIL} & 6 & 3 & 18 \\ 3 & 5 & \text{NIL} & 6 & 4 & \text{NIL} \\ 3 & 6 & 0 & 6 & 5 & \text{NIL} \\ \end{array}$$

So, the $d_{ij}$ values that we get are

$$\begin{pmatrix} 0 & 6 & \infty & 8 & -1 & \infty \\ -2 & 0 & \infty & 2 & -3 & \infty \\ -5 & -3 & 0 & -1 & -6 & -8 \\ -4 & 2 & \infty & 0 & -5 & \infty \\ 5 & 7 & \infty & 9 & 0 & \infty \\ 3 & 5 & 10 & 7 & 2 & 0 \end{pmatrix} .$$

## 25.3-2

What is the purpose of adding the new vertex $s$ to $V'$, yielding $V'$?

This is only important when there are negative-weight cycles in the graph. Using a dummy vertex gets us around the problem of trying to compute $-\infty + \infty$ to find $\hat w$. Moreover, if we had instead used a vertex $v$ in the graph instead of the new vertex $s$, then we run into trouble if a vertex fails to be reachable from $v$.

## 25.3-3

Suppose that $w(u, v) \ge 0$ for all edges $(u, v) \in E$. What is the relationship between the weight functions $w$ and $\hat w$?

If all the edge weights are nonnegative, then the values computed as the shortest distances when running Bellman-Ford will be all zero. This is because when constructing $G'$ on the first line of Johnson's algorithm, we place an edge of weight zero from s to every other vertex. Since any path within the graph has no negative edges, its cost cannot be negative, and so, cannot beat the trivial path that goes straight from $s$ to any given vertex. Since we have that $h(u) = h(v)$ for every $u$ and $v$, the reweighting that occurs only adds and subtracts $0$, and so we have that $w(u, v) = \hat w(u, v)$

## 25.3-4

Professor Greenstreet claims that there is a simpler way to reweight edges than the method used in Johnson's algorithm. Letting $w^* = \min_{(u, v) \in E} \{w(u, v)\}$, just define $\hat w(u, v) = w(u, v) - w^*$ for all edges $(u, v) \in E$. What is wrong with the professor's method of reweighting?

It changes shortest paths. Consider the following graph. $V = \{s, x, y, z\}$, and there are 4 edges: $w(s, x) = 2$, $w(x, y) = 2$, $w(s, y) = 5$, and $w(s, z) = -10$. So we'd add $10$ to every weight to make $\hat w$. With $w$, the shortest path from $s$ to $y$ is $s \to x \to y$, with weight $4$. With $\hat w$, the shortest path from $s$ to $y$ is $s \to y$, with weight $15$. (The path $s \to x \to y$ has weight $24$.) The problem is that by just adding the same amount to every edge, you penalize paths with more edges, even if their weights are low.

## 25.3-5

Suppose that we run Johnson's algorithm on a directed graph $G$ with weight function $w$. Show that if $G$ contains a $0$-weight cycle $c$, then $\hat w(u, v) = 0$ for every edge $(u, v)$ in $c$.

If $\delta(s, v) - \delta(s, u) \le w(u, v)$, we have

$$\delta(s, u) \le \delta(s, v) + (0 - w(u, v)) < \delta(s, u) + w(u, v) - w(u, v) = \delta(s, u),$$

which is impossible, thus $\delta(s, v) - \delta(s, u) = w(u, v)$, $\hat w(u, v) = w(u, v) + \delta(s, u) - \delta(s, v) = 0$.

## 25.3-6

Professor Michener claims that there is no need to create a new source vertex in line 1 of $\text{JOHNSON}$. He claims that instead we can just use $G' = G$ and let $s$ be any vertex. Give an example of a weighted, directed graph $G$ for which incorporating the professor's idea into $\text{JOHNSON}$ causes incorrect answers. Then show that if $G$ is strongly connected (every vertex is reachable from every other vertex), the results returned by $\text{JOHNSON}$ with the professor's modification are correct.

In this solution, we assume that $\infty - \infty$ is undefined, in particular, it's not $0$.

Let $G = (V, E)$, where $V = {s, u}$, $E = \{(u, s)\}$, and $w(u, s) = 0$. There is only one edge, and it enters $s$. When we run Bellman-Ford from $s$, we get $h(s) = \delta(s, s) = 0$ and $h(u) = \delta(s, u) = \infty$. When we reweight, we get $\hat w(u, s) = 0 + \infty - 0 = \infty$. We compute $\hat\delta(u, s) = \infty$, and so we compute $d_{us} = \infty + 0 - \infty \ne 0$. Since $\delta(u, s) = 0$, we get an incorrect answer.

If the graph $G$ is strongly connected, then we get $h(v) = \delta(s, v) < \infty$ for all vertices $v \in V$. Thus, the triangle inequality says that $h(v) \le h(u) + w(u, v)$ for all edges $(u, v) \in E$, and so $\hat w(u, v) = w(u, v) + h(u) - h(v) \ge 0$. Moreover, all edge weights $\hat w(u, v)$ used in Lemma 25.1 are finite, and so the lemma holds. Therefore, the conditions we need in order to use Johnson's algorithm hold: that reweighting does not change shortest paths, and that all edge weights $\hat w(u, v)$ are nonnegative. Again relying on $G$ being strongly connected, we get that $\hat\delta(u, v) < \infty$ for all edges $(u, v) \in E$, which means that $d_{uv} = \hat\delta(u, v) + h(v) - h(u)$ is finite and correct.