8  Shortest Paths

“UNIX is basically a simple operating system, but you have to be a genius to understand the simplicity.”
– Dennis Ritchie

For a weighted graph G=(V, E), the edge weights are given by a function w\colon E\to\mathbb{R} mapping each to a real-valued weight. For example, see the weighted graph below:

drawGraph([0, 1, 2, 3, 4, 5], [[0, 3], [1, 4], [3, 1], [3, 2], [5, 3], [0, 5]], -1, [], [], [2, 1, 3, 2, 1, 0.5]);

A path p in G is denoted by the sequence of vertices \langle v_0,v_1,\ldots,v_k\rangle forming the path. The weight w(p) of path p is the sum of the weights of its constituent edges: w(p)=\sum_{i=1}^k w(v_{i-1}, v_i).

Exercise 8.1 In the graph above, compute the weight of the path p, given by the vertices \langle 0, 3, 1, 4\rangle.

The shortest-path weight \delta(u, v) from u to v is defined by \delta(u, v)=\begin{cases} \min\{w(p)\colon u\overset{p}{\leadsto} v\}&\text{ if }v\text{ is reachable from }u \\ \infty&\text{ otherwise.} \end{cases}

Exercise 8.2 In the graph above, compute the shortest-path weight from 0 to 4.

A shortest path from vertex u to v is then defined as any path u\overset{p}{\leadsto} v with weight w(p)=\delta(u, v).

Exercise 8.3 In the graph above, compute the shortest-path weight from 0 to 4. Also, describe a shortest path.

Exercise 8.4 (Optimal Substructure) Show that subpaths of shortest paths are shortest paths.

We have already seen that the breath-first-search (BFS) is a shortest-path algorithm—if the graph has unit weight for all edges. This is chapter, we discuss variations of the problem of finding shortest-paths between vertices in a graphs.

8.1 Single-Source

We first visit the single-source shortest-paths problem: given a graph G=(V, E), find a shortest path from a given source vertex s\in V to every vertex v\in V.

Exercise 8.5 (Negative-weight Cycles) Explain what would happen to the shortest-paths problem if there was a cycle with a negative weight.

Hint: See the picture below and compute the shortest-path distance from 0 to 3.

drawGraph([0, 1, 2, 3, 4, 5], [[0, 3], [4, 1], [3, 1], [2, 3], [5, 3], [0, 5],[2, 4],[1,2]], -1, [], [], [2, 1, 30, 2, 1, 0.5,-2, -1]);

Exercise 8.6 (Shortest-paths and Cycles) Can a shortest path contain a cycle—even when the edges have positive weights?

Hint: See the picture below and compute the shortest-path distance from 1 to 2.

drawGraph([0, 1, 2, 3, 4, 5], [[3, 0], [1, 4], [1, 3], [3, 2], [5, 3], [0, 5]], -1, [], [], [2, 1, 3, 2, 1, 0.5]);

Belman-Ford Algorithm

\begin{algorithm} \caption{BellmanFord} \begin{algorithmic} \Procedure{Bellman-Ford}{$G, s, w$} \State{▷ Initialize source} \For{each vertex $v\in G.V$} \State{$v.d=\infty$} \EndFor \State{$s.d=0$} \State{▷ Main subroutine} \For{$i=1$ to $|G.V|-1$} \For{each edge $(u,v)\in G.E$} \State{▷ Relax edge} \If{$v.d>u.d + w(u, v)$} \State{$v.d = u.d + w(u,v)$} \EndIf \EndFor \EndFor \State{▷ Find negative-cycle} \For{each edge $(u,v)\in G.E$} \If{$v.d>u.d + w(u, v)$} \Return{False} \EndIf \EndFor \Return{True} \EndProcedure \end{algorithmic} \end{algorithm}

Demo

viewof n = Inputs.range([5, 10], {
  value: 5,
  step: 1,
  label: `n`
});
viewof m = Inputs.range([0, n * n], {
  value: 5,
  step: 1,
  label: `m`
});
viewof s = Inputs.range([0, n], {
  value: 0,
  step: 1,
  label: `s`
});

viewof start = Inputs.button(`Initialize`, {
  reduce: () => {
    D.forEach((d, i) => {D[i] = '∞'});
    D[s] = 0;
    PI.length = 0;

    mutable done = false;
    mutable i = 0;
    mutable j = 0;
  }
});

V = d3.range(n);
D = d3.range(n).map((d) => '');
W = d3.range(m).map((d) => d3.randomInt(-5, 10)());
edge_generator = function(n, m) {
  const rand = d3.randomInt(0,n);
  const res = [];
  
  while(res.length < m) {
    let u = rand(); let v = rand();
    if(u == v) continue;
    if(res.filter((e) => e[0] == u && e[1] == v || e[0] == v && e[1] == u).length > 0) continue;

    res.push([u, v]);
  }
  return res;
};
E = edge_generator(n, m);
PI = [];
mutable done = true;
mutable i = 0;
mutable j = -1;

{
  start; relax;
  return drawGraph(V, E, s, D, PI, W, j);
}

viewof inc_i = Inputs.button(`Increment i : ${i}↦${i+1}`, {
  value: null,
  disabled: j != m || i == n,
  reduce: () => {
    mutable j = 0;
    mutable i = mutable i + 1;
  }
});
viewof relax = Inputs.button(`Relax edge`, {
  value: null,
  disabled: done || j == m,
  reduce: () => {
    let u = E[j][0];
    let v = E[j][1];
    if((D[u] != '∞') && (D[v] == '∞' || (D[v] > D[u] + W[j]))) {
        D[v] = D[u] + W[j];
        PI.push([u, v]);
    }
    mutable j = mutable j + 1; 
  }
});

Exercise 8.7 (Shortest-paths and Cycles) Describe the time-complexity of BELLMAN-FORD.

Solution. \mathcal{O}(V^2 + VE).

8.2 All-Sources

We now compute shortest paths between all pairs of vertices in a graph. An application of all-pairs shortest paths is to determine the diameter of a network: the longest of all shortest paths. If a directed graph models a communication network, with the weight of an edge indicating the time required for a message to traverse a communication link, then the diameter gives the longest possible transit time for a message in the network.

Given a graph G=(V, E) and a weight function w:E\to\mathbb{R}, our goal is to find, for every pair of vertices u,v\in V, a shortest (least-weight) path from u to v so that the weight of a path is the sum of the weights of its constituent edges.

What is the time-complexity of running BELLMAN-FORD on every vertex of the graphs in order to compute all-pairs shortest paths?

Solution. \mathcal{O}(V^4).

Dynamic Programming

Let l_{ij}^(r) be the minimum weight of any path from vertex i to vertex j that contains at most r edges.

drawGraph = function(V, E, source = -1, d = [], blue = [], w = [], dashed = -1) {
  let result = `Digraph{ size = "5"; node [style=filled shape=circle fixedsize=true]`;
  for (let i = 0; i < V.length; i++) {
    let x = V[i];
    result += `${i} [fillcolor = "white" label = "${x}" fontcolor = "red" xlabel="${d[i] || ''}" shape="${i == source ? 'box' : 'circle'}"];`;
  }
  for (let i = 0; i < E.length; i++) {
    let color = 'black';
    let weight = 1;
    for(let j = 0; j < blue.length; j++) {
      if(E[i][0] == blue[j][0] && E[i][1] == blue[j][1] || E[i][1] == blue[j][0] && E[i][0] == blue[j][1]) {
        color = 'blue';
        weight = 2;
      }
    }
    result += `${E[i][0]}->${E[i][1]} [label="${w[i]}" color="${color}" penwidth="${weight}" style="${dashed == i ? 'dashed' : 'solid'}"];`;
  }

  result += "}";
  return dot`${result}`;
}