Leetcode Problem 2714. Find Shortest Path with K Hops

2714. Find Shortest Path with K Hops

Leetcode Solutions

Dijkstra's Algorithm with Edge Hopping

  1. Initialize a priority queue and a distance array dist with dimensions [n][k+1], all set to infinity, except dist[s][k] which is set to 0.
  2. Add the start node s to the priority queue with a distance of 0 and k hops remaining.
  3. While the priority queue is not empty: a. Dequeue the node u with the smallest distance dist_u and hops remaining hops_u. b. If u is the destination node d, return dist_u as the shortest path length. c. For each neighbor v of u with edge weight w: i. If dist[v][hops_u] can be reduced by taking the edge u-v, update it and enqueue v with the updated distance and hops_u. ii. If hops_u is greater than 0 and dist[v][hops_u-1] can be reduced by 'hopping' over the edge u-v, update it and enqueue v with the distance dist_u and hops_u-1.
  4. If the destination node d is never dequeued, return -1 indicating no path exists within the constraints.
UML Thumbnail

Breadth-First Search (BFS) with Edge Hopping

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...