Shortest Path Coding Problems: 21 Questions with Solutions
21 shortest path coding problems — 13 medium · 8 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 7-day plan.
- Problems: 21
- By difficulty: 13 medium · 8 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
A shortest-path algorithm finds the cheapest route between nodes when edges carry costs — travel times, prices, obstacles to remove. Breadth-first search already solves it when every edge costs the same; with different non-negative weights, Dijkstra's algorithm settles nodes in order of distance using a priority queue; with negative weights or a limit on the number of edges, Bellman–Ford relaxes every edge round by round. The problems here practise choosing between them, running them on grids as well as edge lists, and counting or constraining the shortest routes as well as measuring them.
New to shortest path? Read the Dijkstra's Algorithm tutorial first.
How shortest path works, step by step
edges = A→B 4, A→C 2, C→B 1, B→D 5, C→D 8, C→E 10, D→E 2, D→F 3, E→F 2; source = A- Each node carries a tentative distance from A: 0 for A itself, ∞ for the rest. Every step settles the unsettled node with the smallest one; with no negative weights, no path found later can undercut it.
- Settle A at 0, the only finite distance left. Relaxing its edges: B gets 0 + 4 = 4; C gets 0 + 2 = 2.
- Settle C at 2, the smallest unsettled distance (B 4, C 2). Relaxing its edges: B drops from 4 to 2 + 1 = 3; D gets 2 + 8 = 10; E gets 2 + 10 = 12. A path with more edges can still weigh less.
- Settle B at 3, the smallest unsettled distance (B 3, D 10, E 12). Relaxing its edges: D drops from 10 to 3 + 5 = 8.
- Settle D at 8, the smallest unsettled distance (D 8, E 12). Relaxing its edges: E drops from 12 to 8 + 2 = 10; F gets 8 + 3 = 11.
- Settle E at 10, the smallest unsettled distance (E 10, F 11). Relaxing its edges: F would get 10 + 2 = 12, no better than 11, so it keeps 11.
- Settle F at 11, the last node left. It has no edges to unsettled nodes, so nothing is relaxed, and every node is now settled.
- Every distance is final: B 3, C 2, D 8, E 10, F 11. Following each node's last improving edge back gives the shortest path to F, A → C → B → D → F, cost 11. With a binary heap this is O((V + E) log V).
Shortest Path study plan
10 of the 21 Shortest Path problems (7 medium and 3 hard) over 7 days, about 6 h 50 min in all — the pattern first, then easiest to hardest. After that, the other 11 in the full list below are practice at your own pace. Then move on to Minimum Spanning Tree.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.
- Network Delay Time Medium
Day 2
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Cheapest Flights Within K Stops Medium
- The Maze II Medium
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Number of Ways to Arrive at Destination Medium
- Find the City With the Smallest Number of Neighbors at a Threshold Distance Medium
Day 4
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Floyd Warshall Medium
- Minimum Cost of a Path With Special Roads Medium
Day 5
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
Day 6
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Day 7
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Shortest Path: the essentials
When to reach for it
Weighted edges and the cheapest route: a signal reaching every node, the cheapest flight, the fewest obstacles removed. The weights choose the algorithm. All equal: Breadth-First Search. Only 0 and 1: a deque, 0-cost moves pushed at the front. Non-negative: Dijkstra. Negative, or a cap on edges: Bellman–Ford. All pairs on a few hundred nodes: Floyd–Warshall.
The pattern
Dijkstra keeps a heap of (distance, node) pairs. Pop the smallest, skip it if stale (larger than the distance recorded), and otherwise relax each outgoing edge, pushing any neighbour whose distance improves. A node's distance is final when first popped, which needs every weight to be non-negative.
import heapq
def dijkstra(adj, src): # adj[u] = [(v, w), ...] with w >= 0
dist, heap = {src: 0}, [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue # a stale entry
for v, w in adj[u]:
if d + w < dist.get(v, float("inf")):
dist[v] = d + w
heapq.heappush(heap, (d + w, v))
return dist
Cost
Dijkstra with a binary heap is O((V + E) log V) time and O(V + E) space. 0-1 BFS is O(V + E). Bellman–Ford is O(V × E), or O(k × E) for k rounds. Floyd–Warshall is O(V³).
Common mistakes
- Dijkstra with a negative edge, after which a popped distance is no longer final.
- Marking a node done when it is first pushed, as BFS does; a cheaper route to it can turn up later.
- "At most k stops" by Dijkstra on distance alone, which discards a dearer route with stops to spare; run k + 1 Bellman–Ford rounds, each reading the previous round's copy.
INT_MAXas infinity plus a weight, which overflows in Java or C++.
Start with
- Network Delay Time: Dijkstra from one source, then the largest distance.
- Cheapest Flights Within K Stops: a cap on edges, in Bellman–Ford rounds.
- Minimum Obstacle Removal to Reach Corner: 0-1 BFS on a grid.
All shortest path problems
Medium (13)
- Minimum Time to Reach Destination in Directed Graph Graph, Heap (Priority Queue)
- Digit Operations to Make Two Integers Equal Math, Graph, Heap (Priority Queue)
- Find Minimum Time to Reach Last Room II Array, Graph, Heap (Priority Queue)
- Find Minimum Time to Reach Last Room I Array, Graph, Heap (Priority Queue)
- Find a Safe Walk Through a Grid Array, Breadth-First Search, Graph
- Minimum Cost to Convert String I Array, String, Graph
- Minimum Cost of a Path With Special Roads Array, Graph, Heap (Priority Queue)
- Floyd Warshall Graph, Dynamic Programming
- Find the City With the Smallest Number of Neighbors at a Threshold Distance Graph, Dynamic Programming
- Number of Ways to Arrive at Destination Graph, Dynamic Programming, Topological Sort
- The Maze II Array, Matrix, Graph
- Cheapest Flights Within K Stops Graph, Dynamic Programming
- Network Delay Time Graph, Heap
Hard (8)
- Number of Possible Sets of Closing Branches Bit Manipulation, Graph, Heap (Priority Queue)
- Minimum Weighted Subgraph With the Required Paths Graph, Heap (Priority Queue)
- Reachable Nodes In Subdivided Graph Graph, Heap (Priority Queue)
- Minimum Cost to Make at Least One Valid Path in a Grid Breadth-First Search, Graph, Matrix
- Second Minimum Time to Reach Destination Graph, Breadth-First Search
- Minimum Time to Visit a Cell In a Grid Array, Matrix, Graph
- Minimum Obstacle Removal to Reach Corner Array, Matrix, Graph
- Number of Restricted Paths From First to Last Node Graph, Dynamic Programming, Heap (Priority Queue)
Companies that ask shortest path problems
- Google 18 problems on shortest path
- Amazon 16 problems on shortest path
- Microsoft 4 problems on shortest path
- Airbnb 1 problem on shortest path
- Atlassian 1 problem on shortest path
- Flipkart 1 problem on shortest path
- Meta 1 problem on shortest path
- Mphasis 1 problem on shortest path
- Samsung 1 problem on shortest path
- Uber 1 problem on shortest path
Next topic: Minimum Spanning Tree