You are given a positive integer n which is the number of nodes of a 0-indexed undirected weighted connected graph and a 0-indexed 2D array edges where edges[i] = [ui, vi, wi] indicates that there is an edge between nodes ui and vi with weight wi.
You are also given two nodes s and d, and a positive integer k, your task is to find the shortest path from s to d, but you can hop over at most k edges. In other words, make the weight of at most k edges 0 and then find the shortest path from s to d.
Return the length of the shortest path from s to d with the given condition.
Example 1:
Input: n = 4, edges = [[0,1,4],[0,2,2],[2,3,6]], s = 1, d = 3, k = 2 Output: 2 Explanation: In this example there is only one path from node 1 (the green node) to node 3 (the red node), which is (1->0->2->3) and the length of it is 4 + 2 + 6 = 12. Now we can make weight of two edges 0, we make weight of the blue edges 0, then we have 0 + 2 + 0 = 2. It can be shown that 2 is the minimum length of a path we can achieve with the given condition.
Example 2:
Input: n = 7, edges = [[3,1,9],[3,2,4],[4,0,9],[0,5,6],[3,6,2],[6,0,4],[1,2,4]], s = 4, d = 1, k = 2 Output: 6 Explanation: In this example there are 2 paths from node 4 (the green node) to node 1 (the red node), which are (4->0->6->3->2->1) and (4->0->6->3->1). The first one has the length 9 + 4 + 2 + 4 + 4 = 23, and the second one has the length 9 + 4 + 2 + 9 = 24. Now if we make weight of the blue edges 0, we get the shortest path with the length 0 + 4 + 2 + 0 = 6. It can be shown that 6 is the minimum length of a path we can achieve with the given condition.
Example 3:
Input: n = 5, edges = [[0,4,2],[0,1,3],[0,2,1],[2,1,4],[1,3,4],[3,4,7]], s = 2, d = 3, k = 1 Output: 3 Explanation: In this example there are 4 paths from node 2 (the green node) to node 3 (the red node), which are (2->1->3), (2->0->1->3), (2->1->0->4->3) and (2->0->4->3). The first two have the length 4 + 4 = 1 + 3 + 4 = 8, the third one has the length 4 + 3 + 2 + 7 = 16 and the last one has the length 1 + 2 + 7 = 10. Now if we make weight of the blue edge 0, we get the shortest path with the length 1 + 2 + 0 = 3. It can be shown that 3 is the minimum length of a path we can achieve with the given condition.
Constraints:
2 <= n <= 500n - 1 <= edges.length <= min(104, n * (n - 1) / 2)edges[i].length = 30 <= edges[i][0], edges[i][1] <= n - 11 <= edges[i][2] <= 1060 <= s, d, k <= n - 1s != dProblem Overview: You are given a weighted graph and a limit K representing the maximum number of hops (edges) allowed in the path. The task is to compute the minimum cost from a source node to a destination node while using at most K hops.
Approach 1: BFS with State Tracking (O(K * E) time, O(K * V) space)
One straightforward strategy is to treat each state as (node, hopsUsed) and run a level-based traversal similar to BFS. Instead of tracking only the node, maintain the number of edges taken so far. For each expansion, relax edges while ensuring the hop count does not exceed K. Maintain a distance table dist[node][hops] to avoid revisiting worse states. This works well when the graph edges have uniform or small weights, but it becomes inefficient for large graphs with many weighted edges.
Approach 2: Dynamic Programming / Bellman-Ford Style Relaxation (O(K * E) time, O(V) space)
Another method repeatedly relaxes all edges up to K times. Each iteration represents adding one more hop to the path. Maintain two arrays: the previous iteration's distances and the updated distances for the current hop count. For every edge (u → v, w), update dist[v] = min(dist[v], prev[u] + w). This guarantees the shortest distance using at most K edges. The technique is simple and reliable but scans all edges each iteration, which can be expensive when E is large.
Approach 3: Modified Dijkstra with Hop Constraint (O((V + E) log V) time, O(K * V) space)
The optimal solution adapts shortest path logic using a min priority queue. Each entry in the heap represents a state (cost, node, hopsUsed). Always expand the lowest-cost state first, just like standard graph traversal with Dijkstra. When exploring neighbors, push the next state only if hopsUsed + 1 ≤ K. Track the best cost for each (node, hops) combination to avoid redundant work. Because the heap always processes the cheapest partial path, the algorithm quickly converges to the optimal answer while respecting the hop constraint.
Recommended for interviews: Interviewers typically expect the modified Dijkstra approach. Brute-force BFS or Bellman-Ford style relaxation demonstrates that you understand the hop constraint, but the priority queue optimization shows stronger command of graph algorithms and shortest path techniques. If the graph is large and weighted, Dijkstra with an additional state dimension (node, hops) is the most scalable solution.
First, we construct a graph g based on the given edges, where g[u] represents all neighboring nodes of node u and their corresponding edge weights.
Then, we use Dijkstra's algorithm to find the shortest path from node s to node d. However, we need to make some modifications to Dijkstra's algorithm:
u to node d, but since we can cross at most k edges, we need to record the shortest path length from each node u to node d and the number of edges crossed t, i.e., dist[u][t] represents the shortest path length from node u to node d and the number of edges crossed is t.(dis, u, t) to represent the current shortest path, where dis represents the current shortest path length, and u and t represent the current node and the number of edges crossed, respectively.Finally, we only need to return the minimum value in dist[d][0..k].
The time complexity is O(n^2 times log n), and the space complexity is O(n times k), where n represents the number of nodes and k represents the maximum number of edges crossed.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS with (node, hops) state | O(K * E) | O(K * V) | Small graphs or when edge weights are uniform |
| Bellman-Ford style relaxation | O(K * E) | O(V) | Simple implementation when hop limit is small |
| Modified Dijkstra with priority queue | O((V + E) log V) | O(K * V) | General case with weighted edges and large graphs |
Leetcode 2714. Find Shortest Path with K Hops | Dijkstra's algorithm | Java • Jeezy Leets • 299 views views
Practice Find Shortest Path with K Hops with our built-in code editor and test cases.
Practice on FleetCode