Interesting observation: Did you notice that the problem number 787 (see Boing 787) is a problem related to flights!
Approach 1: Using Dijkstra’s Algorithm
Dijkstra’s algorithm is a standard algorithm for finding the shortest path between two nodes. Here, we have to take the cost of a flight to be the weight and minimize it. Additionally, we have another constraint that there should be at most K stops in between, i.e, there should be at most K+1 edges or K+2 vertices (including src and dst). The easiest approach is to use a Priority Queue (min heap). If you’re not familiar with Dijkstra’s algorithm or its priority queue implementation, please read the article on GeeksForGeeks before proceeding.
We will store a tuple<int, int, int> in the priority queue which represents tuple<cost to reach this node, id of node, number of remaining stops>. To use Dijkstra’s algorithm in this way, we will need to pre-process the given array of flights to convert it into an adjacency list. We use a vector of outgoing edges for each node (vector<vector<pair<int,int>>>) - the pair stores the other end of edge and the weight of edge.
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
priority_queue<tup, vector<tup>, greater<tup>> pq;
vector<vector<pair<int,int>>> graph(n);
for (auto v : flights) graph[v[0]].push_back({v[1], v[2]});
pq.push({0, src, K+1});
while (!pq.empty()) {
auto [cost, node, stops] = pq.top();
pq.pop();
if (node == dst)
return cost;
if (stops == 0)
continue;
for (auto p : graph[node]) {
auto [to_node, weight] = p;
pq.push({cost+weight, to_node, stops-1});
}
}
return -1;
}
Time complexity: O(ElogV)
Approach 2: Bellman Ford Algorithm
Bellman Ford algorithm is another standard approach for finding shortest distance between two nodes. This approach is especially useful when the graph contains negative edge as Dijkstra’s fails in this case. But here we are not taking advantage of that but instead taking advantage of Bellman Ford’s inherent implementation. If you are not familiar with the algorithm, please read the GeeksForGeeks article before proceeding.
The article clearly mentions how the algorithm works: Like other Dynamic Programming Problems, the algorithm calculate shortest paths in bottom-up manner. It first calculates the shortest distances which have at-most one edge in the path. Then, it calculates shortest paths with at-most 2 edges, and so on. After the i-th iteration of outer loop, the shortest paths with at most i edges are calculated.
The last line is pretty interesting for us and exactly what we require in this problem. After the (k+1)-th iteration of the loop, the shortest paths with at most k+1 edges are calculated - this is exactly what we want!
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
int size = flights.size();
// sanity check
if (!size)
return -1;
vector<int> dist(n, INT_MAX);
dist[src] = 0;
for (int i=0; i<K+1; i++) {
vector<int> temp(dist);
for (auto f : flights) {
if (dist[f[0]] == INT_MAX) continue;
temp[f[1]] = min(temp[f[1]], dist[f[0]]+f[2]);
}
swap(temp, dist);
}
return dist[dst] == INT_MAX ? -1 : dist[dst];
}
Time complexity: O(kE)