Shortest path and cycle detection: BFS, Dijkstra, Bellman-Ford

Last week you saw how to store a graph and how to traverse it with BFS/DFS. This week we put those traversals to work: the questions the shortest path from one source (single-source) to every node and is there a cycle in the graph. A “fill in the Dijkstra table” question almost certainly appears in the exam. Alongside it come short questions such as “why is Dijkstra wrong here?” or “is there a cycle in this graph?”.

Golden rules:

1. If there are no weights, BFS is enough. Shortest path = fewest edges = BFS layer.
2. If weights are positive, Dijkstra. At each step pick the node with the smallest distance among the unknown ones, finalize it, and relax its edges.
3. If there is a negative edge, Bellman-Ford. Dijkstra may silently give a wrong answer.
4. The path is read backward from the prev array. Walk from the target to the source, then reverse.
5. In a directed graph, cycle = an edge to a gray node. In an undirected one = an edge whose two ends are in the same set.

Unweighted shortest path: BFS

If the cost of every edge is 1, the shortest path is the path with the fewest edges. Since BFS takes nodes out in order of distance from the source (layer by layer), the distance of a node is final the moment it is first discovered. The rule: dist[w] = dist[v] + 1, prev[w] = v.

An example undirected graph (neighbor lists in ascending order):

      0
     / \
    1   2
     \ /
      3
      |
      4
     / \
    5   6
     \ /
      7

queue          dequeued  discovered (dist)
[0]            0         1(1) 2(1)
[1,2]          1         3(2)
[2,3]          2         -    (3 was already seen)
[3]            3         4(3)
[4]            4         5(4) 6(4)
[5,6]          5         7(5)
[6,7]          6         -
[7]            7         -

BFS dist: [0, 1, 1, 2, 3, 4, 4, 5]
BFS prev: [-1, 0, 0, 1, 3, 4, 4, 5]
BFS path 0->7: [0, 1, 3, 4, 5, 7]

The time is $O(V + E)$: each node enters the queue once, and each edge is looked at once (twice in an undirected graph).

PITFALL · write the distance when discovering, not when dequeuing. Give dist and prev and count it as “seen” the moment you put the node in the queue. Otherwise the same node enters the queue twice.

Dijkstra’s algorithm

The edges have weights and all are non-negative. The idea: the node closest to the source cannot have a shorter path through any other node (each extra edge increases the cost). So finalize (known) the node with the smallest tentative distance and relax the edges leaving it:

$d_u > d_v + w(v,u) \;\Rightarrow\; d_u = d_v + w(v,u),\; prev_u = v$

The steps:

1. d[source] = 0, the others ∞. None is known.
2. From the unknown ones, pick the v with the smallest d. On a tie, pick the smaller label.
3. Make v known. For each unknown neighbor u, relax.
4. Go back to 2 until no unknown remains (or all remaining are ∞).

Worked example

The graph G1 (directed), shown as neighbor lists:

A: B(4) C(1)
B: D(5)
C: B(2) D(8) E(10)
D: E(2) F(6)
E: F(2)
F: -

In the exam the table is filled like this. Each row is one pick; * means known.

step pick  A   B   C   D   E   F
 0    -    0   ∞   ∞   ∞   ∞   ∞
 1    A    0*  4   1   ∞   ∞   ∞
 2    C    0*  3   1*  9   11  ∞
 3    B    0*  3*  1*  8   11  ∞
 4    D    0*  3*  1*  8*  10  14
 5    E    0*  3*  1*  8*  10* 12
 6    F    0*  3*  1*  8*  10* 12*

The program’s output:

Dijkstra order: A C B D E F
Dijkstra final: A=0 B=3 C=1 D=8 E=10 F=12
prev: A=- B=C C=A D=B E=D F=E
  path to F: [A, C, B, D, E, F] cost 12

Two moments to notice: in step 2 the value of B dropped from 4 to 3 (cheaper via C). In step 4, E dropped from 11 to 10. This is relaxation: when you find a better path you update the value and the prev.

TIP · keep a prev column in the table too. If the exam asks for the “path from A to F”, you need to have written down through whom you came at each update. Computing it back afterwards wastes time.

Complexity

When writing it with Java’s PriorityQueue there is no “decreaseKey”. The practical solution: when a distance drops, add the node again with its new value, and if the node that comes out of the queue is already known, skip it (lazy deletion).

PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> x[1] - y[1]);
pq.add(new int[]{src, 0});
while (!pq.isEmpty()) {
    int[] top = pq.poll();
    int v = top[0];
    if (known[v]) continue;          // old copy
    known[v] = true;
    for (int[] e : adj.get(v)) {     // e = {neighbor, weight}
        int u = e[0], w = e[1];
        if (!known[u] && d[v] + w < d[u]) {
            d[u] = d[v] + w;
            prev[u] = v;
            pq.add(new int[]{u, d[u]});
        }
    }
}

Negative edges and Bellman-Ford

Dijkstra’s “finalize the closest” step trusts that an edge found later cannot decrease the distance. A negative edge breaks this trust.

A --2--> B --1--> D
|        ^
5       -4
|        |
+-> C ---+

Dijkstra order: A B D C
Dijkstra final: A=0 B=2 C=5 D=3
BF round 1: A=0 B=1 C=5 D=2

Dijkstra finalized B with 2 and made D 3. C came last; the edge C→B could have lowered B to 1, but B was closed. The real answer is D = 2.

Bellman-Ford makes no picks: in each round it relaxes all the edges in order. Since a shortest path contains at most V−1 edges, V−1 rounds are enough. The time is $O(V \cdot E)$, slower than Dijkstra but it works correctly with negative edges.

Arrays.fill(d, INF);
d[src] = 0;
for (int round = 1; round <= V - 1; round++)
    for (Edge e : edges)
        if (d[e.from] != INF && d[e.from] + e.w < d[e.to])
            d[e.to] = d[e.from] + e.w;

The edge order affects the number of rounds. In the order e1 B→C 2, e2 A→B −1, e3 S→A 4, e4 S→B 5, e5 C→D 3, e6 A→C 6, from S:

BF round 1: S=0 A=4 B=5 C=10 D=inf
BF round 2: S=0 A=4 B=3 C=7 D=10
BF round 3: S=0 A=4 B=3 C=5 D=8
BF round 4: S=0 A=4 B=3 C=5 D=8 (no change)

If nothing changed in a round, you can stop early. If an edge can still be relaxed after V−1 rounds, there is a cycle with a negative total; then the “shortest path” is undefined (by going around the cycle again and again, the cost decreases forever). In the graph S→A 1, A→B 2, B→C −4, C→A 1, the total of A→B→C→A is −1 and the program prints BF negative cycle: true.

PITFALL · the “add a constant to all weights” trick does not work. If you add 5 to every edge to get rid of the negative edge, paths with many edges get penalized more, and the shortest path changes.

Cycle detection

Directed graph: DFS with three colors

• White (0): never seen.
• Gray (1): entered in the DFS, not yet finished (on the recursion stack).
• Black (2): all its descendants are finished.

An edge to a gray node means going back to an ancestor on the current path: a back edge, that is, a cycle. An edge to a black node is not a cycle; that branch is already finished.

0 --> 1 --> 2
|     ^     |
v     |     v
4     +---- 3

DFS goes down in the order 0, 1, 2, 3, and all four are gray. 3→1 goes to a gray node:

G2 directed cycle: true back edge 3->1
DAG directed cycle: false

A directed graph with no cycle is called a DAG. Only DAGs have a topological order; in Kahn’s algorithm (last week), if all nodes cannot be removed, there is also a cycle.

Undirected graph

In an undirected graph, every edge is two-directional, so “the neighbor was already seen” is not always a cycle: the parent you came from has been seen too. Two ways:

• DFS + parent: a seen neighbor that is not the parent means a cycle.
• Union-find: add the edges one by one. If the two ends are already in the same set, this edge closes a cycle. Kruskal (week 13) uses exactly this.

undirected: first cycle-closing edge 1-3

A quick check: in a connected undirected graph, if $E \ge V$ there is definitely a cycle (in a tree $E = V - 1$).

Which algorithm when?

Common mistakes

pick A: B=4 C=1
pick C: B=min(4,1+2)=3 D=9 E=11
pick B: D=min(9,3+5)=8
pick D: E=min(11,8+2)=10 F=14
pick E: F=min(14,10+2)=12
pick F: done

static boolean hasCycle(List<List<Integer>> adj) {
    int[] color = new int[adj.size()];
    for (int v = 0; v < adj.size(); v++)
        if (color[v] == 0 && dfs(adj, v, color)) return true;
    return false;
}
static boolean dfs(List<List<Integer>> adj, int v, int[] color) {
    color[v] = 1;                       // gray
    for (int w : adj.get(v)) {
        if (color[w] == 1) return true; // back edge
        if (color[w] == 0 && dfs(adj, w, color)) return true;
    }
    color[v] = 2;                       // black
    return false;
}