2714. Find Shortest Path with K Hops
Problem Description
You are working with a special type of graph, which is an undirected, weighted, and connected graph represented by a number of nodes and a list of edges. Each edge has a weight, establishing the cost to travel between two nodes. The unique challenge you face is to determine the shortest path from a start node s
to a destination node d
. The twist is the ability to "hop over" certain edges, making their weight effectively zero, but you can only do this for at most k
edges. This "hop" capability allows you to ignore the weight of the selected edges, which can drastically change the result compared to the usual shortest path calculations.
The goal is to use this capability strategically, choosing up to k
edges to skip, in order to minimize the total weight of the path from s
to d
.
Intuition
To tackle this problem, leverage Dijkstra's algorithm, which is commonly used to find the shortest paths between nodes in a weighted graph. Traditionally, Dijkstra's algorithm does not account for being able to bypass any edges. Because of this, you'll need to adapt the algorithm to accommodate the possibility of "hopping over" some edges.
To do this, create a modified graph representation that takes into account both the actual weight of the edges and the number of hops used thus far. Keep track of the shortest distances from the start node s
to all other nodes with various numbers of hops, up to the maximum k
hops allowed. This requires a two-dimensional array where one dimension is the node identifier and the second dimension is the number of hops used. Initialize the distances to infinity to ensure that any explored path will replace the placeholder value.
Use a priority queue to store and quickly access the current shortest path candidates, ordered by their distance. This queue will contain tuples with the current distance, the node identifier, and the number of hops used. Whenever a node is dequeued, examine its neighbors and attempt two types of updates: one where an additional hop is used (if you have hops left), and one where the edge's actual weight is considered in the usual manner.
By doing this at each stage, you are effectively exploring all combinations of used and unused hops, up to the limit k
. After considering all nodes and paths, the shortest distance to the destination node d
can be found by looking at the shortest distances recorded for reaching d
with each possible number of hops, and then taking the minimum.
The underlying Dijkstra's algorithm uses a greedy strategy to guarantee the shortest path is found. By integrating it with the concept of hops, you can extend its utility to this unique scenario, providing an efficient and elegant solution.
Learn more about Graph, Shortest Path and Heap (Priority Queue) patterns.
Solution Approach
Let's break down the implementation of the solution as per the reference approach provided:
-
Graph Construction: We start by constructing a graph
g
that represents the given undirected weighted graph. This is a list of lists, whereg[u]
contains tuples(v, w)
indicating there is an edge from the nodeu
to nodev
with weightw
. This step transforms the edge list into an adjacency list representing the same graph, which is a commonly used data structure for graph algorithms allowing efficient traversal of connected nodes. -
Distance Initialization: Initially, we create a 2D list
dist
filled with infinity values. The dimensions are[n][k + 1]
, wheren
is the number of nodes andk
is the maximum number of hops allowed.dist[u][t]
will store the shortest distance to reach nodeu
using exactlyt
hops. -
Priority Queue: A min-heap priority queue
pq
is used for efficient retrieval of the current shortest path candidate nodes to be evaluated. A tuple(dis, u, t)
is pushed into the queue, wheredis
is the current shortest distance,u
is the node, andt
is the number of hops used to reach nodeu
. -
Dijkstra's Algorithm with Modifications: We adapt Dijkstra's algorithm to deal with hops. We pop a node from the priority queue and look at its neighbors. For each neighbor
v
, we consider two scenarios:- If we have remaining hops (i.e.,
t + 1 <= k
), we consider what happens if we "hop over" the edge tov
. Ifdist[v][t + 1]
is greater than the current distancedis
without adding the weight of the edgew
, we found a shorter path tov
with one more hop. We updatedist[v][t + 1]
and push(dis, v, t + 1)
intopq
. - We also consider the case where we don't use a hop. If the sum of
dis + w
is less thandist[v][t]
, then we found a shorter path without using a hop, and we updatedist[v][t]
and push(dis + w, v, t)
intopq
.
- If we have remaining hops (i.e.,
-
Finding the Shortest Path: After we have processed all possible paths, the shortest path from the start node
s
to the destination noded
can be deduced by finding the minimum distance from all the distances recorded indist[d][0...k]
.
The two main adaptations to the standard Dijkstra's algorithm are:
- The use of a
t
dimension in thedist
array and priority queue tuples to keep track of the number of hops. - Adjusting the path relaxation step to consider both "hopping over" an edge and the actual weight of the edge.
By applying these changes, we maintain the greedy nature of the standard Dijkstra's algorithm, ensuring that the shortest path is found, while also incorporating the additional rules about hopping over edges in an efficient manner.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small graph example to illustrate the solution approach. Our task is to find the shortest path from the start node s
to the destination node d
, with the ability to hop over at most k
edges.
Given Graph Structure:
Let's consider a graph with 4 nodes and some edges with weights between them. Our nodes are 0
to 3
, where 0
is our start node s
and 3
is our destination node d
. Let's use k = 1
, which means we can skip the weight of one edge.
The graph is represented by the following set of edges with weights:
(0, 1)
with weight4
(0, 2)
with weight1
(1, 3)
with weight1
(2, 3)
with weight5
Therefore, our adjacency list representation of the graph, g
, after graph construction would be:
g[0]
:[(1, 4), (2, 1)]
g[1]
:[(0, 4), (3, 1)]
g[2]
:[(0, 1), (3, 5)]
g[3]
:[(1, 1), (2, 5)]
Step-by-Step Walkthrough:
-
Graph Construction: We have already constructed the adjacency list
g
. -
Distance Initialization: We initialize
dist
as a 2D list with dimensions[4][k + 1]
, filled with infinity:dist
=[[inf, inf], [inf, inf], [inf, inf], [inf, inf]]
-
Priority Queue: We start with a priority queue
pq
and push the start node0
with a distance0
and0
hops used:pq
=[(0, 0, 0)]
. -
Dijkstra's Algorithm with Modifications: Now, we start the modified Dijkstra's algorithm:
-
We pop
(0, 0, 0)
frompq
. We updatedist[0][0]
to0
as it's the starting node. -
Checking neighbors of
0
, we have1
and2
. For1
with edge weight4
:- If we hop: since we haven't used any hops yet, we update
dist[1][1]
to0
(0
distance +0
weight because we hopped), and add(0, 1, 1)
topq
. - If we don't hop: we update
dist[1][0]
to4
(0
distance +4
weight), and add(4, 1, 0)
topq
.
- If we hop: since we haven't used any hops yet, we update
-
For
2
with edge weight1
:- If we hop: we update
dist[2][1]
to0
(0
distance +0
weight), and add(0, 2, 1)
topq
. - If we don't hop: we update
dist[2][0]
to1
(0
distance +1
weight), and add(1, 2, 0)
topq
.
- If we hop: we update
-
Next,
pq
has[(0, 1, 1), (0, 2, 1), (4, 1, 0), (1, 2, 0)]
, sorted by distance. -
Processing continues, evaluating each node and its neighbors following the steps outlined, while always selecting the next closest node from the priority queue and updating
dist
considering both hopping and not hopping.
-
-
Finding the Shortest Path: After all possible paths are processed, we check
dist[3]
. The shortest path tod
is the minimum ofdist[3][0]
anddist[3][1]
.
In this example, if we hop from 0
to 2
, and then move from 2
to 3
without hopping, the total distance is 1
(edge (0, 2)
weight) + 5
(edge (2, 3)
weight) = 6
. Without hopping, the path 0 -> 1 -> 3
would have a weight of 5
which is longer than the path using a hop. Therefore, the shortest path using at most k=1
hops is from 0
to 2
using a hop and then to 3
without a hop, yielding a minimum distance of 6
.
Solution Implementation
1from typing import List
2from heapq import heappush, heappop
3from math import inf
4
5class Solution:
6 def shortestPathWithHops(self, num_nodes: int, edges: List[List[int]],
7 source: int, destination: int, max_hops: int) -> int:
8 # Create an adjacency list to store the graph
9 graph = [[] for _ in range(num_nodes)]
10 for start, end, weight in edges:
11 graph[start].append((end, weight))
12 graph[end].append((start, weight))
13
14 # Initialize the distances to infinity, for all nodes and for each number of hops
15 distances = [[inf] * (max_hops + 1) for _ in range(num_nodes)]
16 # The distance to the source node with 0 hops is 0
17 distances[source][0] = 0
18
19 # Priority queue will store tuples of (distance, node, hops)
20 priority_queue = [(0, source, 0)]
21
22 # Continue processing until the priority queue is empty
23 while priority_queue:
24 # Get the node with the minimum distance
25 cur_dist, cur_node, hops = heappop(priority_queue)
26
27 # Explore all adjacent nodes
28 for neighbor, weight in graph[cur_node]:
29 # If we can reach the neighbor with an additional hop and it's beneficial
30 if hops + 1 <= max_hops and distances[neighbor][hops + 1] > cur_dist:
31 distances[neighbor][hops + 1] = cur_dist
32 heappush(priority_queue, (cur_dist, neighbor, hops + 1))
33
34 # If we can reach the neighbor without an additional hop and it offers a shorter path
35 if distances[neighbor][hops] > cur_dist + weight:
36 distances[neighbor][hops] = cur_dist + weight
37 heappush(priority_queue, (cur_dist + weight, neighbor, hops))
38
39 # Calculate the shortest path to the destination allowing for up to max_hops hops,
40 # and return it if possible; return -1 if there is no path.
41 shortest_path = min(distances[destination])
42 return int(shortest_path) if shortest_path != inf else -1
43
1class Solution {
2 public int shortestPathWithHops(int nodes, int[][] edges, int start, int destination, int maxHops) {
3 List<int[]>[] graph = new List[nodes];
4 Arrays.setAll(graph, i -> new ArrayList<>());
5
6 // Construct an adjacency list from the edge list
7 for (int[] edge : edges) {
8 int from = edge[0], to = edge[1], weight = edge[2];
9 graph[from].add(new int[] {to, weight});
10 graph[to].add(new int[] {from, weight});
11 }
12
13 // Priority queue will be used to process nodes in order of distance
14 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
15
16 // Starting with the start node, distance of 0 and 0 hops
17 pq.offer(new int[] {0, start, 0});
18
19 // Initialize distance array holding minimum distances for each hop count
20 int[][] distances = new int[nodes][maxHops + 1];
21 final int infinity = 1 << 30;
22 for (int[] row : distances) {
23 Arrays.fill(row, infinity);
24 }
25 distances[start][0] = 0;
26
27 // Process nodes until priority queue is empty
28 while (!pq.isEmpty()) {
29 int[] current = pq.poll();
30 int currentDistance = current[0], currentNode = current[1], currentHops = current[2];
31
32 // Check each neighbour of the current node
33 for (int[] edge : graph[currentNode]) {
34 int nextNode = edge[0], edgeWeight = edge[1];
35
36 // If hopping to the next node without increasing distance is possible and beneficial
37 if (currentHops + 1 <= maxHops && distances[nextNode][currentHops + 1] > currentDistance) {
38 distances[nextNode][currentHops + 1] = currentDistance;
39 pq.offer(new int[] {currentDistance, nextNode, currentHops + 1});
40 }
41
42 // If going to the next node and increasing the distance is beneficial
43 if (distances[nextNode][currentHops] > currentDistance + edgeWeight) {
44 distances[nextNode][currentHops] = currentDistance + edgeWeight;
45 pq.offer(new int[] {currentDistance + edgeWeight, nextNode, currentHops});
46 }
47 }
48 }
49
50 // Find the minimum distance to the destination within the allowed number of hops
51 int result = infinity;
52 for (int i = 0; i <= maxHops; ++i) {
53 result = Math.min(result, distances[destination][i]);
54 }
55
56 // Return inf if no path satisfies the conditions
57 return result == infinity ? -1 : result;
58 }
59}
60
1#include <vector>
2#include <queue>
3#include <cstring>
4#include <tuple>
5#include <algorithm>
6using namespace std;
7
8class Solution {
9public:
10 int shortestPathWithHops(int n, vector<vector<int>>& edges, int start, int destination, int k) {
11 // Create a graph representation with adjacency lists
12 vector<vector<pair<int, int>>> graph(n);
13 for (const auto& edge : edges) {
14 int u = edge[0], v = edge[1], weight = edge[2];
15 graph[u].emplace_back(v, weight);
16 graph[v].emplace_back(u, weight);
17 }
18
19 // Declare a min-heap priority queue to maintain (distance, node, hops) tuples
20 priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> minHeap;
21 // Add the starting node to the queue with distance 0 and 0 hops
22 minHeap.emplace(0, start, 0);
23
24 // Initialize the distance array, setting all distances to a large value
25 int distances[n][k + 1];
26 memset(distances, 0x3f, sizeof(distances)); // Using 0x3f to fill the array with a high number
27 distances[start][0] = 0;
28
29 // Process the nodes in the queue
30 while (!minHeap.empty()) {
31 auto [currentDistance, currentNode, hops] = minHeap.top();
32 minHeap.pop();
33
34 // Iterate through all neighbors of the current node
35 for (auto &[neighbor, weight] : graph[currentNode]) {
36 // If within hops limit and the current path has a better distance, update and enqueue
37 if (hops + 1 <= k && distances[neighbor][hops + 1] > currentDistance) {
38 distances[neighbor][hops + 1] = currentDistance;
39 minHeap.emplace(currentDistance, neighbor, hops + 1);
40 }
41 // If taking the edge leads to a better distance, update and enqueue
42 if (distances[neighbor][hops] > currentDistance + weight) {
43 distances[neighbor][hops] = currentDistance + weight;
44 minHeap.emplace(currentDistance + weight, neighbor, hops);
45 }
46 }
47 }
48
49 // Calculate the minimum distance to the destination node within k hops
50 int minDistance = *min_element(distances[destination], distances[destination] + k + 1);
51 // If the minimum distance is still the initialized high value, return -1 (path not found)
52 return (minDistance == 0x3f3f3f3f) ? -1 : minDistance;
53 }
54};
55
1type Edge = [number, number, number]; // Define a type for edges, represented as tuple [source, destination, weight]
2type Graph = Map<number, Array<[number, number]>>; // Graph type with an adjacency list
3
4const buildGraph = (n: number, edges: Edge[]): Graph => {
5 const graph = new Map<number, Array<[number, number]>>();
6 for (const [u, v, weight] of edges) {
7 if (!graph.has(u)) graph.set(u, []);
8 if (!graph.has(v)) graph.set(v, []);
9 graph.get(u)?.push([v, weight]);
10 graph.get(v)?.push([u, weight]);
11 }
12 return graph;
13};
14
15const shortestPathWithHops = (n: number, edges: Edge[], start: number, destination: number, k: number): number => {
16 // Create a graph representation with adjacency lists
17 const graph = buildGraph(n, edges);
18
19 // Define a type for priority queue elements: [distance, node, hops]
20 type PriorityQueueElement = [number, number, number];
21 // Create a min-heap priority queue to maintain the nodes
22 const minHeap: PriorityQueueElement[] = [];
23 const enqueue = (element: PriorityQueueElement) => {
24 minHeap.push(element);
25 minHeap.sort(([distanceA], [distanceB]) => distanceA - distanceB);
26 };
27 const dequeue = () => minHeap.shift();
28
29 // Add the starting node to the queue with distance 0 and 0 hops
30 enqueue([0, start, 0]);
31
32 // Initialize the distance array, setting all distances to a large value
33 const distances: number[][] = Array.from({ length: n }, () => Array(k + 1).fill(Infinity));
34 distances[start][0] = 0;
35
36 // Process the nodes in the queue
37 while (minHeap.length) {
38 const [currentDistance, currentNode, hops] = dequeue()!;
39
40 // Iterate through all neighbors of the current node
41 graph.get(currentNode)?.forEach(([neighbor, weight]) => {
42 // If within hops limit and the current path has a better distance, update and enqueue
43 if (hops + 1 <= k && distances[neighbor][hops + 1] > currentDistance) {
44 distances[neighbor][hops + 1] = currentDistance;
45 enqueue([currentDistance, neighbor, hops + 1]);
46 }
47
48 // If taking the edge leads to a better distance, update and enqueue
49 if (distances[neighbor][hops] > currentDistance + weight) {
50 distances[neighbor][hops] = currentDistance + weight;
51 enqueue([currentDistance + weight, neighbor, hops]);
52 }
53 });
54 }
55
56 // Calculate the minimum distance to the destination node within k hops
57 const minDistance = Math.min(...distances[destination]);
58 // If the minimum distance is still the initialized high value, return -1 (path not found)
59 return isFinite(minDistance) ? minDistance : -1;
60};
61
62// You can now call the function 'shortestPathWithHops' with the parameters as required.
63
Time and Space Complexity
The time complexity of the given code is O(E + n * k * log(n))
, where E
represents the edges in the given graph, n
is the number of nodes, and k
is the maximum number of hops. The E
term comes from the initial edge iteration to construct the adjacency list, and n * k * log(n)
comes from the while loop where we consider each hop for each node and the priority queue (min-heap) operations which have O(log n)
complexity. Specifically, if all nodes are connected to all other nodes the edges number would be close to n^2
, making the overall time complexity look like O(n^2 * log n)
.
The space complexity of the code is O(n * k)
, which is used to store distances for every node at every possible hop from 0 to k
.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]
?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
8
1public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
12
1class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Shortest Path Between A and B Prereq BFS on Graph problems graph_bfs Given an unweighted connected graph return the length of the shortest path between two nodes A and B in terms of the number of edges Assume there always exists a path between nodes A and B Input graph
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
Want a Structured Path to Master System Design Too? Don’t Miss This!