Shortest Path Practice Test: Dijkstra, BFS, 0-1 BFS in C++
A timed shortest-path checkpoint: ten questions on BFS, 0-1 BFS and Dijkstra's lazy deletion, then all-distances Dijkstra and counting shortest paths in C++.
- Course: Competitive Programming study plan
- Module: Shortest paths: BFS, 0-1 BFS, Dijkstra
- Kind: Checkpoint — cleared at 70%
- Reading time: 45 min
- Runtime: Clang 18 · C++20
Checkpoint — Shortest paths is the checkpoint that closes the Shortest paths: BFS, 0-1 BFS, Dijkstra module: a graded quiz and whole-program exercises, passed at 70%.
Instructions
A 45-minute timed checkpoint on module 8: choosing BFS, 0-1 BFS or Dijkstra from the weights, and writing Dijkstra correctly under a clock.
How it works. Ten questions and two programs, in 45 minutes from when you start the timer. 70% on the questions and both programs accepted clears the module.
Before you start, make sure you can answer these from memory:
- Which algorithm fits equal weights, 0/1 weights, non-negative weights, negative weights.
- What
greater<>does to apriority_queue, and why the distance goes first in the pair. - What the line
if (d > dist[u]) continue;skips, and why it is safe. - Why path sums are
long long, and how an unreachable vertex is printed.
The programs are Dijkstra's distances from vertex 1 to every vertex with weights up to 10^9, and the number of shortest paths to vertex n modulo 10^9 + 7.
Common questions
How do you count the number of shortest paths with Dijkstra?
Keep ways[v] beside dist[v]. When relaxing u → v finds a strictly shorter distance, set ways[v] = ways[u]; when it finds an equal one, add ways[u] to ways[v]. Because vertices settle in distance order, ways[u] is final before it is used.
Why must the heap pair put the distance first?
std::pair compares its first member first, so {dist, vertex} orders the heap by distance. With {vertex, dist} the heap would pop by vertex number and settle vertices at wrong distances.
Exercises
Dijkstra to every vertex
A directed graph has vertices 1 to n and m weighted edges. Print the shortest distance from vertex 1 to every vertex, -1 for one that cannot be reached.
Input: n m, then m lines u v w (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 2·10^5, 1 ≤ w ≤ 10^9). Output: n integers on one line, separated by spaces.
5 6
1 2 4
1 3 1
3 2 2
2 4 5
3 4 8
4 5 3prints
0 3 1 8 11How many shortest routes
A directed graph has vertices 1 to n and m weighted edges. Print the length of the shortest path from 1 to n and the number of different shortest paths modulo 10^9 + 7 (two paths differ when their edge sequences differ), separated by a space. Print -1 alone if n cannot be reached.
Input: n m, then m lines u v w (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 2·10^5, 1 ≤ w ≤ 10^9). Output: one line.
4 5
1 2 1
1 3 1
2 4 1
3 4 1
1 4 3prints
2 2In this module: Shortest paths: BFS, 0-1 BFS, Dijkstra
← Shortest paths — BFS, 0-1 BFS and Dijkstra · Topological sort — Kahn's algorithm and DP on a DAG →