Back to course

Exercise 5

Shortest-Path Algorithms

Modified WeightsAlgorithm AnalysisMedium Difficulty

Exam Format & Expectations

Shortest-path questions typically involve:

  1. Modified weight functions - Prove/disprove algorithm correctness
  2. Special objectives - Minimize edges, then weight
  3. Algorithm modifications - Adapt Dijkstra/Bellman-Ford
  4. Correctness proofs - Show the modification works

Key insight: Weight modifications often encode multiple objectives into a single weight function.

The Weight Modification Technique

Linear Combination

Combine two objectives with different priorities:

w'(e) = α · primary(e) + secondary(e)

Choose α large enough that primary objective dominates

The Big-C Technique

Choose C larger than any possible path weight:

w'(e) = w(e) + C

where C > sum of all original weights

Full Exam Solution: Minimum Edges with Tiebreaker (2024)

Problem:

Find a path P from s to t such that:

  1. P uses as few edges as possible
  2. Among all paths with minimum edges, P has smallest total weight

Proposed Algorithm:

1. T = Σ w(e) for all e ∈ E 2. For every edge e: w'(e) = w(e) + T + 1 3. Run Dijkstra with weights w' 4. Output the resulting path P

Prove or disprove: This algorithm correctly solves the problem.

Full Solution(10/10)

The algorithm is CORRECT.

Proof:

1. Weight transformation analysis:

For any path P with k edges and total original weight W:

w'(P) = Σe∈P w'(e) = Σe∈P (w(e) + T + 1) = W + k(T + 1)

2. Edge count dominates:

Since T = Σe∈E w(e) and W ≤ T for any path:

  • • If path P1 has k1 edges
  • • If path P2 has k2 edges with k1 < k2
  • • Then: w'(P1) < k1(T+1) + T < k2(T+1) < w'(P2)

3. Weight tiebreaking:

For paths with the same number of edges k:

w'(P1) < w'(P2) ⟺ W1 + k(T+1) < W2 + k(T+1) ⟺ W1 < W2

4. Conclusion:

Dijkstra minimizes w'(P), which ensures P has minimum edges first, then minimum weight among paths with that many edges. ✓

Example: Bottleneck Shortest Path

Problem:

Find a path from s to t that minimizes the maximum edge weight on the path.

Wrong Approach

Setting w'(e) = w(e)2 doesn't work! Squaring doesn't preserve the bottleneck property.

Correct Approach

Can't solve with weight modification. Instead:

  1. Binary search on the bottleneck value B
  2. For each B, use BFS on subgraph with edges ≤ B
  3. Find minimum B where path exists

Common Weight Modification Patterns

Pattern 1: Minimize Primary, Then Secondary

w'(e) = primary(e) · C + secondary(e)

where C > max possible secondary cost

Pattern 2: Count + Weight

w'(e) = (T + 1) + w(e)

Minimizes edge count, breaks ties by weight

Pattern 3: Lexicographic Ordering

w'(e) = C2 · metric1(e) + C · metric2(e) + metric3(e)

Ensures strict priority ordering between metrics

Exam Strategy

Proving Correctness

  1. 1. Show how weights encode objectives
  2. 2. Prove primary objective dominates
  3. 3. Verify tiebreaking works correctly
  4. 4. Conclude algorithm finds optimal path

Finding Counterexamples

  1. 1. Look for small graphs (3-4 nodes)
  2. 2. Try extreme weight values
  3. 3. Check if objectives conflict
  4. 4. Draw the example clearly

Quick check: If C isn't big enough (e.g., C = max weight instead of sum), the algorithm usually fails. This is a common source of counterexamples.

Previous: Flow AlgorithmsNext: Flow Theory