Model Artifact: Algorithm Benchmark Note

Scenario

A learner compares three shortest-path implementations for sparse road-like graphs in Semester 2.

Completed learner-quality example

Question

For nonnegative weighted sparse graphs with up to 200,000 edges, should the project use binary-heap Dijkstra, adjacency-matrix Dijkstra, or Bellman-Ford?

Experimental setup

• Hardware: laptop, 8 performance cores, plugged in, quiet background load.
• Dataset: generated connected graphs with V ∈ {1k, 10k, 50k} and average degree near 4.
• Measurement: median of 9 warm runs after one discarded warmup.
• Correctness guard: all implementations compared on 100 small random graphs against a brute-force oracle.

Results

Vertices	Edges	Binary-heap Dijkstra	Matrix Dijkstra	Bellman-Ford
1,000	4,012	6 ms	43 ms	310 ms
10,000	40,238	74 ms	4,910 ms	34,800 ms
50,000	201,044	492 ms	timed out at 60 s	timed out at 60 s

Interpretation

Binary-heap Dijkstra scales with the sparse edge count and is the only candidate that stays comfortably below the interactive latency target. Matrix Dijkstra wastes work scanning absent edges, while Bellman-Ford pays for repeated relaxation passes we do not need because the graph has no negative weights.

Decision

Use adjacency lists plus binary-heap Dijkstra. Keep Bellman-Ford only in the notes as the correct alternative if a later problem introduces negative edges without negative cycles.

Reproducibility notes

The benchmark script pins the random seed, prints graph density, verifies every output distance vector on small cases, and stores raw run logs beside the summarized table.

How to read this example

• Passing: Has a question, setup, measurements, and a decision rather than a table alone.
• Strong: Separates correctness checks from performance checks and explains why asymptotic expectations match the measured trend.
• Portfolio-worthy: Captures reproducibility details and clearly states when the decision would change.