Approach Summary
Bellman-Ford for k+1 rounds. Or modified Dijkstra with state (cost, node, stops_remaining). dp[node] after k+1 relaxations = answer.
How to Recognize This Pattern
- "Cheapest path with at most k intermediate stops"
- K-limited BFS (Bellman-Ford) beats unconstrained Dijkstra here
Complexity Analysis
Time Complexity
O(K × E)
Space Complexity
O(V)
Tags
Dynamic Programming DFS BFS Graph Heap Shortest Path