Find Shortest Path with K Hops

Find Shortest Path with K Hops

What is this problem about?

The Find Shortest Path with K Hops interview question is a graph optimization problem. You are given a weighted graph and a target number of "hops" $k$. In this version, a "hop" allows you to traverse any edge for a cost of 0. Your goal is to find the minimum distance from a source to a destination using at most $k$ such hops.

Why is this asked in interviews?

Goldman Sachs asks the Find Shortest Path coding problem to see if you can adapt standard pathfinding algorithms like Dijkstra to include an extra "resource" or "budget." It evaluations your ability to expand the state space of an algorithm—moving from "shortest distance to node $u$" to "shortest distance to node $u$ using $j$ hops."

Algorithmic pattern used

This is solved using Modified Dijkstra's Algorithm.

1. Expanded State: The priority queue should store (distance, node, hops_remaining).
2. Transitions: From a node u with hops_remaining = j:
   • Regular Edge: Move to neighbor v with cost $W$. New state: (dist + W, v, j).
   • Use a Hop: If $j > 0$, move to neighbor v with cost 0. New state: (dist, v, j - 1).
3. Visited Array: Maintain a 2D array minDist[node][hops_remaining] to prune paths.

Example explanation

Path: A --(10)--> B --(20)--> C, $k = 1$.

• Option 1 (No hops): $10 + 20 = 30$.
• Option 2 (Hop A-B): $0 + 20 = 20$.
• Option 3 (Hop B-C): $10 + 0 = 10$. The minimum distance is 10.

Common mistakes candidates make

• Standard Dijkstra: Forgetting that the "number of hops" is a crucial part of the state. Reaching a node with a longer distance but more hops left might be better than reaching it with a shorter distance but 0 hops.
• BFS for Hops: Trying to use BFS because of the "hops" keyword. BFS only works for unweighted edges; since other edges have weights, Dijkstra is necessary.
• Negative Weights: Not checking if the graph has negative weights (though rare in these problems), which would require Bellman-Ford.

Interview preparation tip

When an algorithm has a "budget" (like $k$ skips, $k$ stops, or $k$ hops), the budget almost always becomes a second dimension in your visited/distance array and your Priority Queue state. This is a high-signal Graph interview pattern.