2 · Shortest paths + priority queues + hash tables

DPV Ch 42 exam problemsMCQs Most likely problems: a Dijkstra table (DPV 4.1 style), a Bellman–Ford table (DPV 4.2 style), "why does Dijkstra fail with negative edges" (Quiz 6, Ex 4.8, 4.9), or a lecture-solved design exercise (4.3, 4.15, 4.18, 4.21). Heaps and hash tables are MCQ material.

0. Which algorithm? (router)

All of them use the same update(u, v): \(\text{dist}(v) = \min(\text{dist}(v), \text{dist}(u) + \ell(u,v))\). They differ only in which edges get updated, in what order, and how many times.

1. BFS distances

procedure bfs(G, s)
  for all u in V: dist(u) = ∞
  dist(s) = 0
  Q = [s]                        (FIFO queue)
  while Q is not empty:
    u = eject(Q)
    for all edges (u, v) in E:
      if dist(v) = ∞:
        inject(Q, v)
        dist(v) = dist(u) + 1
        prev(v) = u

The queue holds vertices at distance \(d\) followed by vertices at distance \(d+1\), never more than two layers, because of FIFO order. \(O(|V|+|E|)\). Dijkstra is BFS with the FIFO queue replaced by a priority queue keyed by tentative distance.

2. Dijkstra

procedure dijkstra(G, ℓ, s)       (requires ℓ(e) ≥ 0)
  for all u in V:
    dist(u) = ∞
    prev(u) = nil
  dist(s) = 0
  H = makequeue(V)               (keys = dist)
  while H is not empty:
    u = deletemin(H)             (dist(u) is now final)
    for all edges (u, v) in E:
      if dist(v) > dist(u) + ℓ(u, v):
        dist(v) = dist(u) + ℓ(u, v)
        prev(v) = u
        decreasekey(H, v)

Operation count: 1 makequeue, \(|V|\) deletemin, up to \(|V|+|E|\) insert/decreasekey.

How to fill the DPV-style table

1. One row per vertex, one column per iteration. Column 0: source 0, everyone else ∞.
2. Each iteration: deletemin the vertex with the smallest tentative dist among those not yet removed. Ties: alphabetically first. Write which vertex was removed at the top of the column.
3. Update only its out-neighbours: new value = min(old, dist(u) + edge). Copy every other value unchanged. When a value drops, also change prev.
4. Removed vertices never change again. The last iteration usually changes nothing; still write the column.
5. Shortest-path tree = the prev edges.

Worked: DPV 4.1 (Dijkstra from A)

Why Dijkstra is correct

Let \(R\) be the set of removed vertices. When \(u\) is removed with tentative distance \(d\) (the smallest outside \(R\)), any other path from \(s\) to \(u\) must leave \(R\) at some first vertex \(v \notin R\). That prefix already costs at least \(\text{dist}(v) \ge d\), and the rest of the path has non-negative length, so the path costs \(\ge d\). Hence \(d\) is final. DPV's invariant: after each iteration, all of \(R\) is at distance \(\le\) some \(d\) and everything outside at \(\ge d\), and \(\text{dist}(u)\) is the shortest path using only intermediate vertices in \(R\).

The step that breaks with negative edges: "the rest of the path has non-negative length."

Running time by priority queue (DPV §4.5)

• Dense graph (\(|E| = \Omega(|V|^2)\)): array wins. Binary heap wins once \(|E| < |V|^2/\log|V|\).
• Best \(d \approx |E|/|V|\) (the average degree): good on both sparse and dense graphs.
• Dijkstra's shortest-path tree is not in general a minimum spanning tree.

3. Negative edges break Dijkstra

Quiz 6: 3-vertex graph, no negative cycle, Dijkstra fails

Edges S→A 2, S→B 3, B→A −2. No cycles at all.

• Remove S: A = 2, B = 3.
• Remove A (2 < 3). Dijkstra declares dist(A) = 2 final.
• Remove B: but S→B→A costs \(3 - 2 = 1 < 2\). True dist(A) = 1. Dijkstra's answer 2 is wrong.

Ex 4.8: "add a large constant to every edge, then run Dijkstra"

Not valid. Adding \(c\) to every edge adds \(c\cdot k\) to a path with \(k\) edges, so paths with more edges are penalized more. The shortest path can change. Lecture counterexample, source \(u\):

Original: \(u\to v\to w\) costs \(-2+2 = 0\), beats \(u\to w = 2\). Distances 0, −2, 0. After +3: \(u\to v\to w\) costs \(1+5 = 6\), direct \(u\to w\) costs 5, so Dijkstra returns \(u\to w\), which is the wrong path in the original graph.

Ex 4.9: only the edges leaving \(s\) are negative. Can Dijkstra fail?

No, it works (assuming no negative cycle, i.e. the negative edges out of \(s\) do not combine with a path back into \(s\) to form one).

Proof. A shortest path never needs to revisit \(s\), so every shortest path to \(u\ne s\) has the form \(s\to v\leadsto u\), where only the first edge can be negative and the rest are positive. Dijkstra removes \(s\) first and sets \(\text{dist}(v)=\ell(s,v)\) for every out-neighbour. From then on, run the usual argument: when \(u\) is removed with value \(d\), any other path leaves \(R\) at some \(v\notin R\) with \(\text{dist}(v)\ge d\), and every edge after \(v\) is not an edge out of \(s\), so it is positive. The path costs \(\ge d\). The one place the proof used non-negativity is still true.

4. Bellman–Ford

procedure update((u, v) in E)
  dist(v) = min{dist(v), dist(u) + ℓ(u, v)}

procedure bellman-ford(G, ℓ, s)    (no negative cycles)
  for all u in V:
    dist(u) = ∞
    prev(u) = nil
  dist(s) = 0
  repeat |V| − 1 times:
    for all e in E:
      update(e)

• Safe: every finite dist(v) is the length of some real path, so it never drops below the true distance.
• Enough: a shortest path has at most \(|V|-1\) edges. Round \(i\) fixes at least the \(i\)th edge of it, so \(|V|-1\) rounds suffice. \(O(|V||E|)\).
• Early stop: if a whole round changes nothing, stop.
• Negative cycle: run round \(|V|\). If any dist still decreases, a negative cycle is reachable from \(s\) (follow prev from the changed vertex to find it).

Table format

Rows = vertices, columns = rounds (0 = initial). Process edges in one fixed order every round and say what order you used. Within a round, an update uses values already changed earlier in the same round. The intermediate columns depend on the edge order; the final distances do not.

Worked: DPV 4.2 (Bellman–Ford from S)

5. Shortest (and longest) paths in a DAG

procedure dag-shortest-paths(G, ℓ, s)
  linearize G                    (DFS, decreasing post)
  for all u in V: dist(u) = ∞
  dist(s) = 0
  for each u in V, in linearized order:
    for all edges (u, v) in E:
      update(u, v)

Every path in a DAG visits vertices in topological order, so every shortest path's edges get updated in sequence. Negative edges are fine. \(O(|V|+|E|)\). For longest paths, use max instead of min (or negate all lengths). That only works because a DAG has no cycles; longest path in a general graph is NP-hard.

Example: topological order S, C, A, B, D, E. Shortest from S: S 0, C 2, A 1, B 7, D 5, E 6. Longest from S: S 0, C 2, A 6 (via C), B 12, D 13, E 14.

6. Lecture-solved and HW exercises

for all u in V: d(u) = ∞; usp(u) = true
d(s) = 0
H = makequeue(V)
while H is not empty:
  u = deletemin(H)
  for all edges (u, v) in E:
    if d(v) > d(u) + ℓ(u, v):
      d(v) = d(u) + ℓ(u, v)
      usp(v) = usp(u)            (a strictly better path: unique iff u's is)
      decreasekey(H, v)
    else if d(v) = d(u) + ℓ(u, v):
      usp(v) = false             (a second shortest path)

for all u in V: d(u) = ∞; best(u) = ∞
d(s) = 0; best(s) = 0
H = makequeue(V)
while H is not empty:
  u = deletemin(H)
  for all edges (u, v) in E:
    if d(v) > d(u) + ℓ(u, v):
      d(v) = d(u) + ℓ(u, v)
      best(v) = best(u) + 1
      decreasekey(H, v)
    else if d(v) = d(u) + ℓ(u, v):
      if best(v) > best(u) + 1: best(v) = best(u) + 1

7. Priority queues (binary heap)

• Complete binary tree, filled level by level, left to right. Heap order: each key \(\le\) its children's keys, so the minimum is at the root.
• Array layout, positions \(1..n\): node \(j\) has parent \(\lfloor j/2\rfloor\), children \(2j\) and \(2j+1\). Height \(\lfloor\log_2 n\rfloor\).
• insert: put the new key in the first free position, bubble up (swap with parent while smaller). \(O(\log n)\).
• decreasekey: lower the key, bubble up from its current position. \(O(\log n)\).
• deletemin: return the root, move the last element to the root, sift down (swap with the smaller child while bigger). \(O(\log n)\).
• makeheap: put all \(n\) items in the array, then sift down positions \(n, n-1, \ldots, 1\). \(O(n)\), not \(O(n\log n)\). Heapsort = makeheap + \(n\) deletemins = \(O(n\log n)\).
• \(d\)-ary heap: parent of \(j\) is \(\lceil (j-1)/d\rceil\), children \((j-1)d+2, \ldots, jd+1\). Height \(\Theta(\log n/\log d)\): faster insert, slower deletemin.

Example: heap [2, 5, 3, 9, 6, 8]. Insert 1 at position 7; parent 3 holds 3 → swap; parent 1 holds 2 → swap. Result [1, 5, 2, 9, 6, 8, 3]. Deletemin: return 1, move 3 to the root, children 5 and 2 → swap with 2. Result [2, 5, 3, 9, 6, 8].

8. Hash tables (week 7 notes)

Dictionary ADT: search, insert, delete. Expected \(O(1)\) search under reasonable assumptions, worst case \(\Theta(n)\). Table size is proportional to the number of keys stored, not the number of possible keys.

9. Self-check