Skip to main content
Talentd

Find Shortest Path with K Hops - Solution & Explanation

HardPremiumFree on FleetCodeGraphHeap (Priority Queue)Shortest Path12 min readAsked at: Goldman Sachs
Practice this problem

Problem Statement

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 <= 500
  • n - 1 <= edges.length <= min(104, n * (n - 1) / 2)
  • edges[i].length = 3
  • 0 <= edges[i][0], edges[i][1] <= n - 1
  • 1 <= edges[i][2] <= 106
  • 0 <= s, d, k <= n - 1
  • s != d
  • The input is generated such that the graph is connected and has no repeated edges or self-loops

Approach Overview

Problem 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.

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:

  • We need to record the shortest path length from each node 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.
  • We need to use a priority queue to maintain the current shortest path, but since we need to record the number of edges crossed, we need to use a triple (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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS with (node, hops) stateO(K * E)O(K * V)Small graphs or when edge weights are uniform
Bellman-Ford style relaxationO(K * E)O(V)Simple implementation when hop limit is small
Modified Dijkstra with priority queueO((V + E) log V)O(K * V)General case with weighted edges and large graphs

Video Solution

Leetcode 2714. Find Shortest Path with K Hops | Dijkstra's algorithm | Java • Jeezy Leets • 318 views views

Frequently Asked Questions

Is Find Shortest Path with K Hops easy or hard?
Find Shortest Path with K Hops is typically classified as a Hard graph problem. The difficulty comes from modeling the extra state (number of hops) while still applying an efficient shortest path algorithm. Candidates must adapt Dijkstra or dynamic programming rather than using a basic BFS or standard shortest path template.
Find Shortest Path with K Hops Python/Java solution
Most implementations use Dijkstra with a priority queue. In Python, the heapq module stores (cost, node, hops) states. In Java, a PriorityQueue with a custom comparator performs the same role. C++ uses std::priority_queue with a min-heap pattern, while Go typically uses container/heap.
What is the best approach for Find Shortest Path with K Hops?
The most efficient approach is a modified Dijkstra algorithm using a priority queue. Each state stores (cost, node, hopsUsed), allowing the algorithm to track both distance and hop count. The priority queue ensures the lowest-cost path is expanded first while enforcing the K-hop constraint. This runs in about O((V + E) log V) time for most graphs.
How to solve Find Shortest Path with K Hops in O((V+E) log V)?
Use a modified Dijkstra algorithm. Push states (distance, node, hopsUsed) into a min-heap and always expand the smallest distance first. When visiting neighbors, push the next state only if hopsUsed + 1 ≤ K and the cost improves the stored distance for that node-hop pair. This keeps the search efficient while respecting the hop limit.
Is Find Shortest Path with K Hops asked at Google/Amazon/Meta?
Graph shortest-path variants with constraints frequently appear in interviews at companies like Google, Amazon, and Meta. Problems involving hop limits, stop limits, or edge constraints are common follow-ups to standard Dijkstra questions because they test deeper understanding of graph state modeling.
What data structure is used in Find Shortest Path with K Hops?
The core data structure is a min heap (priority queue) used in Dijkstra’s algorithm. The heap stores states containing the current node, total cost, and number of hops taken. A distance table or visited structure indexed by (node, hops) prevents processing worse paths repeatedly.
What is the time complexity of Find Shortest Path with K Hops?
The optimal priority-queue solution runs in O((V + E) log V) time with O(K * V) space because each node may be visited with different hop counts. Simpler approaches such as Bellman-Ford style relaxation or BFS with state tracking take O(K * E) time since edges are processed repeatedly for each hop level.

Ready to solve this problem?

Practice Find Shortest Path with K Hops with our built-in code editor and test cases.

Practice on FleetCode
Previous

Clone Graph

Next

Course Schedule