Problem Description
There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.
You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.
Solution
This can be solved by using Bellman Ford. Here, we will performn the relaxation of the nodes k+1 times as we can have maximum k+1 edges (k stops) between the source and destination.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
//init dist/cost array
int[] distance = new int[n];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[src] = 0;
//temo dist/cost array
int[] tempDistance = new int[n];
Arrays.fill(tempDistance, Integer.MAX_VALUE);
tempDistance[src] = 0;
//use max k+1 edges (k stops)
for(int i=1; i<=k+1; i++){
//update the dist/cost for each reachable node
for(int j=0; j<flights.length; j++){
int u = flights[j][0];
int v = flights[j][1];
int w = flights[j][2];
//if the current source is reachable
//and the distance from the current node is less than previously calculated value
//then update the current min distance in the temp distance array
if(distance[u] != Integer.MAX_VALUE && distance[u] + w < tempDistance[v])
tempDistance[v] = Math.min(distance[v], distance[u] + w);
}
//copy values from temp array to original array
for(int x=0; x<n; x++) distance[x] = tempDistance[x];
}
//if destination is not reachable, return -1
if(distance[dst] == Integer.MAX_VALUE) return -1;
return distance[dst];
}
}