Graphs and shortest paths: adjacency lists, BFS and Dijkstra
Represent a road network as a graph, find shortest routes with breadth-first search and Dijkstra's algorithm, rebuild the route from predecessors, and search every order of stops.
A graph is just things (nodes) and connections (edges). Road networks, dependencies, social networks and state machines are all graphs, and a handful of algorithms covers most of what you'll need.
Representing a graph
For most real graphs (many nodes, few edges each), use an adjacency list: for each node, the list of its outgoing edges.
roads:
depot -> [(market, 7 min), (station, 3 min)]
station -> [(market, 2 min)]
market -> []In C++ that's std::unordered_map<std::string, std::vector<Edge>>, or map names to integer ids
once and use std::vector<std::vector<Edge>>, which is faster and simpler to index. One-way roads
are one edge; two-way roads are two.
Breadth-first search
When all edges cost the same, BFS finds the shortest path by exploring in rings: everything one step away, then two steps, and so on.
queue = [start]; seen = {start}
while queue not empty:
node = pop front
for each neighbour of node not in seen:
seen.add(neighbour); parent[neighbour] = node; push back neighbourDijkstra's algorithm
With different costs, always expand the node with the smallest known distance next, using a priority queue:
dist[start] = 0; push (0, start)
while queue not empty:
(d, node) = pop smallest
if d > dist[node]: continue # an outdated entry, skip it
for each (next, cost) of node:
if d + cost < dist[next]:
dist[next] = d + cost
parent[next] = node
push (dist[next], next)In C++, std::priority_queue is a max-heap; pass std::greater<> to pop the smallest:
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>>.
The "skip outdated entries" line replaces the decrease-key operation the textbook version
needs. The cost is O((V + E) log V).
Rebuilding the route
Dijkstra gives distances. To get the route itself, record each node's predecessor whenever
you improve its distance (the parent above), then walk back from the destination:
route = [destination]
while route.last != start: route.append(parent[route.last])
reverse routeIf the destination never got a distance, there is no route: return "unreachable" rather than an empty route that looks like a valid answer. When two routes tie, the order you relax edges in decides which one you get, so a ticket that says "the route through fewer stops wins" needs a tie-break in the comparison.
Closing roads
To answer "what if this road is closed?", don't delete and re-add edges; keep a set of closed edges and skip them while relaxing. Reopening is removing from the set.
Trying every order of stops
"Visit these 6 stops and come back, as fast as possible" is the travelling salesman problem. There's no fast general algorithm, but for up to about 8–10 stops you can try every order:
- Run Dijkstra from each stop (and the depot) once, to get a table of shortest times between every pair.
- Try every permutation of the stops (
std::next_permutationon a sorted list), summing times from the table. - Skip a permutation as soon as its partial sum exceeds the best total so far (pruning).
8 stops is 40,320 orders: instant. 15 stops is over a trillion: that's when you need heuristics, and the ticket will say so. Build it in delivery routes for Roundtrip Couriers.
Questions and answers
- When can I use BFS instead of Dijkstra?
- When every edge has the same cost (or no cost, just 'number of hops'). With different travel times, BFS finds the route with the fewest roads, not the fastest, so you need Dijkstra.
- Does Dijkstra's algorithm work with negative edge weights?
- No. It assumes that once a node is taken from the queue, no cheaper route to it exists, which negative edges can break. Road networks, travel times and distances are never negative, so it fits them perfectly.
Practise it in a project
These projects put this guide to work, with tickets, tests and code review.
Read next
- Big-O in practice: amortised cost, worst cases and memory
What Big-O tells you on the job: the costs of common operations, amortised O(1), inputs that trigger the worst case, memory as a cost, and when to measure instead of guessing.