Algorithms / Shortest Path Modeling
Least You Need to Know: Shortest-Path Modeling and State Graph Design
Many interview and contest problems become easier once you model them as shortest-path problems. The art is to choose the right state graph: vertices represent states or positions, edges represent allowed moves, and weights represent transition cost. Once the model is correct, the algorithm choice follows from the edge weights.
The least you need to know
- Model vertices as the states you can be in and edges as legal transitions.
- Edge weights should encode exactly the cost being optimized.
- Choose BFS for unweighted transitions and weighted shortest-path algorithms otherwise.
- A super-source can represent multiple starting points.
- The modeling step is often harder than the algorithm itself.
Key notation
state graph
graph whose vertices represent problem states and edges represent legal moves
super-source
an extra source connected to multiple initial states
transition cost
the weight associated with one allowed move
Tiny worked example
- In a grid, each cell can be a vertex.
- Legal moves to neighboring cells become edges.
- If each move costs 1, BFS solves the shortest-path problem.
- If terrain costs vary, edge weights model those costs and a weighted shortest-path algorithm is needed.
Common mistakes
- Students often jump to Dijkstra before checking whether the graph is actually unweighted.
- If the state space is wrong, the shortest-path algorithm can be perfectly implemented and still solve the wrong problem.
- Super-sources are a standard way to encode multiple possible starts cleanly.
How to recognize this kind of problem
- The prompt describes states and legal moves more clearly than it names a graph.
- There is a cost to accumulate over a sequence of moves.
- A multi-source variant appears naturally.