Problem

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.

Examples

Example 1:

Input: n = 4, flights =[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Example 2:

graph TD;
A(0) -- "100" --> B(1)
B -- "100" --> C(2)
A -- "500" --> C

linkStyle default stroke:blue
linkStyle 0 stroke-width:4px,stroke:red
linkStyle 1 stroke-width:4px,stroke:red
  
Input: n = 3, flights =[[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

Example 3:

graph TD;
A(0) -- "100" --> B(1)
B -- "100" --> C(2)
A -- "500" --> C

linkStyle default stroke:blue
linkStyle 2 stroke-width:4px,stroke:red
  
Input: n = 3, flights =[[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

Constraints

  • 1 <= n <= 100
  • 0 <= flights.length <= (n * (n - 1) / 2)
  • flights[i].length == 3
  • 0 <= fromi, toi < n
  • fromi != toi
  • 1 <= pricei <= 10^4
  • There will not be any multiple flights between two cities.
  • 0 <= src, dst, k < n
  • src != dst

Solution

Constraints of the flights are super important. One of them is k<n. There are multiple solutions to this problem:

  • Dijkstra’s Algo - O(V^2)
  • Floyd Warshall - O(V^3)
  • Bellman Ford - O(V^3) - Takes care of negative cycle, but not needed as flight costs are positive
  • BFS ( + optional Heap)
  • DFS + Pruning - Easy
  • DFS + Memo - Easy

Also, how will we represent our graph? This is a weighted graph. We can use following representation: Weighted Graph Representation - Adjacency List of Pair and map.

Lets look at the common build graph function:

public Map<Integer, List<int[]>> buildGraph(int[][] flights) {
	for (int i = 0; i < n; i++) {
		graph.put(i, new LinkedList<>());
	}
	
	Map<Integer,List<int[]>> map=new HashMap<>();
	for(int[] f:flights) {
		// map.putIfAbsent(f[0],new ArrayList<>());
		map.get(f[0]).add(new int[]{i[1],i[2]});
	}

}

Note that we are running for (i=0; i<n;i++) loop above. The reason is it helps in case when the graph is not connected. If we are sure that graph is connected, we can just remove this loop and uncomment map.putIfAbsent(f[0],new ArrayList<>());.

Now we can use buildGraph across multiple approaches

Method 1 - DFS + Pruning

Pretty straightforward implementation. Traverse all the children of the source upto k stops. If at any point we reach the destination, store the min of the answer and the current cost.

Now the question is why are we passing flights as K+1 to DFS? Because we have K stops at maximum, hence K+1 flights between those stops.

Code

Java
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
	Map<Integer, List<int[]>> graph = buildGraph(n, flights);
	boolean[] visited = new boolean[n];

	// I am passing fare as array object as Java is pass by value
	int[] fare = new int[1];
	fare[0] = Integer.MAX_VALUE;
	
	//find cheapest price with k stops(k + 1 flights)
	dfs(graph, src, dst, K+1, fare, 0, visited);

	return fare[0] == Integer.MAX_VALUE ? -1 : fare[0];
}

private void dfs(Map<Integer, List<int[]>> graph, int src, int dst, int K, int[] fare, int currentCost, boolean[] visited) {
	if (K == 0) {
		return;
	}
	if (src == dst) {
		fare[0] = Math.min(fare[0], currentCost);
		return;
	}

	visited[src] = true;

	for (int[] e : graph.get(src)) {
		int eVertex = e[0], eCost = e[1];
		//Pruning, check the sum of current price and next cost. 
		if (!visited[eVertex] && currentCost + eCost <= fare[0]) {
			dfs(graph, eVertex, dst, K - 1, fare, currentCost + eCost, visited);
		}
	}

	visited[src] = false;
}

Note that we are doing pruning by checking currentCost+eCost <= fare[0], otherwise the algo will become slower.

Method 2 - DFS + Memo

The only thing which appears to be different from a standard DFS call is the memoization part. Since, the nodes are higher in number and we can easily get a TLE re-calculating the distances, it’s better to store the computed values for later use.

So, we now return cost from dfs method. As, we are storing fare in dp array, we dont have to carry fare as well and remove visited set.

Code

Java
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
	Map<Integer, List<int[]>> graph = buildGraph(n, flights);

	int[][] dp = new int[n+1][K+2];
	
	//find cheapest price with k stops(k + 1 flights)
	int ans = dfs(graph, src, dst, K+1, dp);

	return ans;
}

private int dfs(Map<Integer, List<int[]>> graph, int src, int dst, int K, int[][] dp) {
	if (src == dst) {
		return 0;
	}

	if (K == 0) {
		return Integer.MAX_VALUE;
	}

	if (dp[src][K] != 0) return dp[src][K];

	
	int minCost = Integer.MAX_VALUE
	for (int[] e : graph.get(src)) {
		int eVertex = e[0], eCost = e[1];
		
		int currCostRemaining = dfs(graph, eVertex, dst, K - 1, dp);
		ans = Math.min(ans, eCost+currCostRemaining);
		
	}

	dp[src][K] = ans;
	return ans;
}

Method 3 - Bottom up Tabular DP

No need to build graph here.

Code

Java
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
	int[][] dp = new int[k+2][n];
	for(int i=0; i<=k+1; i++){
		Arrays.fill(dp[i],Integer.MAX_VALUE);    
	}
	//fly from src to scr cost 0
	for(int i=0; i<=k+1; i++){
		dp[i][src] = 0;    
	}
	
	for(int i=1; i<=k+1; i++){
		for(int[] f: flights){
			int u = f[0];
			int v = f[1];
			int w = f[2];
			if(dp[i-1][u]!=Integer.MAX_VALUE){
				dp[i][v] = Math.min(dp[i][v],dp[i-1][u]+w);
			}
		}
	}
	return dp[k+1][dst] == Integer.MAX_VALUE ? -1 : dp[k+1][dst];
}

Method 4 - BFS + Pruning

Unlike BFS, now we simultaneously traverse all the possible path going out from source for upto k steps. If the ans is found in between, we store the min of the current ans with the newly found one. A modification to the standard bfs design, we pass the starting cost a 0 to the queue as well and go on adding to it.

Code

Java
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
	Map<Integer, List<int[] >> graph = buildGraph(n, flights);
	int step = 0;
	Queue<int[] > q = new LinkedList<>();
	q.offer(new int[] {
		src, 0
	});
	int ans = Integer.MAX_VALUE;
	while (!q.isEmpty()) {
		int size = q.size();
		for (int i = 0; i<size; i++) {
			int[] curr = q.poll();
			if (curr[0] == dst)
				ans = Math.min(ans, curr[1]);
			if (!map.containsKey(curr[0]))
				continue;
			for (int[] f: map.get(curr[0])) {
				if (curr[1] + f[1] > ans) //Pruning
					continue;
				q.offer(new int[] {
					f[0], curr[1] + f[1]
				});
			}
		}
		if (step > (K+1)) // again remember, K stops, K+1 flights
			break;
	}
	return ans == Integer.MAX_VALUE ? -1 : ans;
}

Method 5 - Dijkstra’s Algo

Much like BFS, but use a PriorityQueue based on the cheapest cost. Incorporate the stop limit to individual paths to traverse upto k stops.

Code

Java
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
	Map<Integer, List<int[] >> map = buildGraph(n, flights);
	PriorityQueue<int[] > q = new PriorityQueue<>((a,b) -> Integer.compare(a[0],b[0]));
	
	q.offer(new int[] {
		0, src, K + 1
	});
	while (!q.isEmpty()) {
		int[] c = q.poll();
		int cost = c[0];
		int curr = c[1];
		int stop = c[2];
		if (curr == dst)
			return cost;
		if (stop > 0) {
			for (int[] e: map.get(curr)) {
				int eVertex = e[0], eCost = e[1];
				q.add(new int[] {
					cost + eCost, eVertex, stop - 1
				});
			}
		}
	}
	return -1;
}

Method 6 - Bellman Ford

Much like BFS, run the algorithm K times, if the answer exists, it should be stored in the helper matrix

Code

Java
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
	int[] cost = new int[n];
	Arrays.fill(cost, Integer.MAX_VALUE);
	cost[src] = 0;
	for (int i = 0; i<= K; i++) {
		int[] temp = Arrays.copyOf(cost, n);
		for (int[] f: flights) {
			int curr = f[0], next = f[1], price = f[2];
			if (cost[curr] == Integer.MAX_VALUE)
				continue;
			temp[next] = Math.min(temp[next], cost[curr] + price);
		}
		cost = temp;
	}
	return cost[dst] == Integer.MAX_VALUE ? -1 : cost[dst];
}