10.23 Common Shortest-Path Patterns and Interview Problems
Learning shortest-path algorithms is only the first step.
10.23 Common Shortest-Path Patterns and Interview Problems
Learning shortest-path algorithms is only the first step.
The next challenge is recognizing when a problem can be solved using them.
Many interview questions, programming contests, and production systems disguise shortest-path problems behind different stories:
- Mazes
- Transformations
- Scheduling
- Navigation
- Resource optimization
- State exploration
The underlying graph is often hidden.
This recipe presents the most common shortest-path patterns and shows how to identify them quickly.
Problem
Given a problem that does not explicitly mention graphs, determine whether it can be modeled as a shortest-path problem and identify the appropriate algorithm.
The key question becomes:
What are the vertices, what are the edges, and what does path cost represent?
Once those elements are identified, the solution often becomes straightforward.
Pattern 1: Minimum Number of Steps
Problem statement:
Find the minimum number of moves.
Find the minimum number of operations.
Find the fewest transformations.
Examples:
Word ladder
Maze solving
Number transformations
Puzzle moves
Model:
Vertex = state
Edge = valid move
Weight = 1
Algorithm:
BFS
Example:
Start: 1
Operations:
+1
×2
Target: 11
Graph:
1 -> 2
1 -> 2
2 -> 3
2 -> 4
...
The shortest sequence of operations is simply the shortest path.
Recognition clue:
Every action costs exactly one step.
Pattern 2: Weighted Navigation
Problem statement:
Minimum travel time
Minimum travel cost
Minimum energy consumption
Cheapest route
Examples:
Road networks
Transportation systems
Flight planning
Robot navigation
Model:
Vertex = location
Edge = movement
Weight = travel cost
Algorithm:
Dijkstra
Recognition clue:
Costs are nonnegative and vary.
Pattern 3: Nearest Facility
Problem statement:
Nearest hospital
Nearest warehouse
Nearest charging station
Nearest exit
Examples:
Emergency response
Logistics
Service coverage
Model:
Multiple source vertices
Algorithm:
Multi-source BFS
or:
Multi-source Dijkstra
Recognition clue:
Find nearest among many starting locations.
Pattern 4: Grid Navigation
Problem statement:
Shortest route in a grid
Minimum moves in a maze
Robot path planning
Example:
S . . .
# # . .
. . . G
Model:
Vertex = cell
Edge = valid movement
Algorithms:
| Grid Type | Algorithm |
|---|---|
| Uniform movement cost | BFS |
| Weighted terrain | Dijkstra |
| Target known with heuristic | A* |
| Costs 0 and 1 | 0-1 BFS |
Recognition clue:
Movement occurs between neighboring cells.
Pattern 5: State-Space Search
Problem statement:
Transform configuration A into B
Solve puzzle
Reach target state
Examples:
Sliding puzzle
Rubik's Cube
Configuration changes
Game states
Model:
Vertex = state
Edge = valid transition
Algorithms:
BFS
Dijkstra
A*
depending on transition costs.
Recognition clue:
States and transitions exist even though no graph is shown.
Pattern 6: Shortest Path with Constraints
Problem statement:
May break one wall
May use one coupon
May refuel once
May skip one edge
Example:
Reach destination
while breaking at most one wall.
Model:
State must include extra information.
Instead of:
(row, col)
use:
(row, col, wallBroken)
Algorithms:
BFS
Dijkstra
depending on edge weights.
Recognition clue:
Current capabilities affect future decisions.
Pattern 7: Keys and Doors
Problem statement:
Collect keys
Open doors
Unlock regions
Example:
S . a
# # .
A . G
Model:
(row, col, keyMask)
The key inventory becomes part of the state.
Algorithms:
BFS
or:
Dijkstra
Recognition clue:
Future movement depends on previously collected items.
Pattern 8: Currency Exchange and Arbitrage
Problem statement:
Detect profitable cycles
Find arbitrage opportunities
Transformation:
weight = -log(exchangeRate)
Multiplication becomes addition.
Profitable cycles become:
Negative cycles
Algorithm:
Bellman-Ford
Recognition clue:
Repeated transactions can increase value.
Pattern 9: Dependency Chains
Problem statement:
Project scheduling
Build systems
Task dependencies
Pipeline execution
Example:
Compile parser
before compiler
Compile compiler
before executable
Model:
DAG
Algorithms:
Topological sort
DAG shortest paths
Recognition clue:
Dependencies form an acyclic structure.
Pattern 10: All-Pairs Distances
Problem statement:
Distance between every pair
Travel times between all cities
Network latency matrix
Algorithms:
Dense Graph
Floyd-Warshall
Sparse Graph
Johnson's algorithm
Recognition clue:
Every source matters.
Pattern 11: Alternative Routes
Problem statement:
Top K routes
Backup routes
Alternative recommendations
Examples:
GPS alternatives
Network failover
Flight recommendations
Algorithms:
K shortest paths
Yen's algorithm
Eppstein's algorithm
Recognition clue:
Need more than one optimal solution.
Pattern 12: Bidirectional Search Problems
Problem statement:
Source and destination known.
Graph extremely large.
Examples:
Road networks
Social networks
Large state spaces
Algorithm:
Bidirectional BFS
Bidirectional Dijkstra
Recognition clue:
Only one source-target path is needed.
Pattern 13: Heuristic Search Problems
Problem statement:
Large search space
Known destination
Geometric information available
Examples:
GPS routing
Game AI
Robotics
Algorithm:
A*
Recognition clue:
A reasonable estimate of remaining distance exists.
The Hidden Graph Checklist
When encountering a new problem, ask:
What Is the State?
Examples:
Location
Word
Configuration
Inventory
Position + fuel
Position + keys
What Is a Move?
Examples:
Step
Transformation
Operation
Transition
What Is the Cost?
Examples:
1 per move
Travel time
Energy
Risk
Money
What Is the Goal?
Examples:
Reach destination
Reach configuration
Minimize cost
Detect cycle
If you can answer all four questions, you likely have a graph problem.
Interview Pattern Recognition Table
| Problem Clue | Likely Algorithm |
|---|---|
| Fewest moves | BFS |
| Unweighted graph | BFS |
| Weights 0 and 1 | 0-1 BFS |
| Positive weights | Dijkstra |
| Negative weights | Bellman-Ford |
| DAG dependencies | DAG shortest paths |
| Grid with obstacles | BFS |
| Weighted grid | Dijkstra |
| Known destination + coordinates | A* |
| Nearest facility | Multi-source BFS |
| All pairs | Floyd-Warshall / Johnson |
| Alternative routes | K shortest paths |
| Negative cycle detection | Bellman-Ford |
This table covers a large percentage of practical shortest-path questions.
Why These Patterns Repeat
Most shortest-path problems arise from optimization.
Optimization problems usually ask:
Minimum
Maximum
Best
Cheapest
Fastest
Shortest
Whenever you see these words, consider whether:
States
+
Transitions
=
Graph
The graph may be hidden, but the optimization structure often remains obvious.
Common Mistakes
Do not focus immediately on the algorithm.
Focus first on the state representation.
Do not build explicit graphs when neighbors can be generated dynamically.
Do not ignore hidden state variables such as keys, fuel, coupons, or permissions.
Do not use BFS when costs differ.
Do not overlook multi-source formulations. Many "nearest" problems become trivial once multiple starting points are recognized.
Discussion
Experienced problem solvers rarely begin with:
Which algorithm should I use?
Instead they begin with:
What is the graph?
Once the graph is identified:
Unweighted?
Weighted?
DAG?
Negative edges?
Single source?
All pairs?
the algorithm often selects itself.
The most valuable skill is therefore graph recognition rather than algorithm memorization.
Takeaway
Many shortest-path problems are disguised as puzzles, routing tasks, transformations, scheduling systems, or optimization challenges. The key is to identify states, transitions, costs, and goals. Once a hidden graph emerges, familiar algorithms such as BFS, Dijkstra, Bellman-Ford, A*, Floyd-Warshall, or multi-source search usually apply directly. In interviews and production systems alike, recognizing the graph is often the hardest part of the solution.