Solution Developed In:
The Question
For this article we will be covering Leetcode's '787. Cheapest Flights Within K Stops' question. An Advanced Graph question.
Question:
There are
n
cities connected by some number offlights
. You are given an arrayflights
whereflights[i]
=[fromi, toi, pricei]
indicates that there is a flight from cityfrom
tocity
to
with costprice
.You are also given three integers
src
,dst
, andk
, return the cheapest price fromsrc
todst
with at mostk
stops. If there is no such route, return-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.
Explaining The Question
This Question is rated Medium. Which is I would say is in-accurate, even if you know Bellman-Ford or Dijkstra you'll still have an issue solving this question, especially if you're using Dijkstra because Leetcode Runtime constraints are very strict. Due to how strict this question is, I would say this is a hard question if you're using Dijkstra and medium if using Bellman-Ford. For this question, we're going to use Dijkstra to solve it.
Dijkstra is a greedy algorithm that finds the shortest path from a source to a destination. It works a lot like Breadth First Search. We're going to explore the cheapest flights from src
to dst
within k
stops.
How do you think Google Maps knows the shortest distance (Be distance or cost) between your house and New Yorks Airport? Shortest Path algorithms like Dijkstra's Algorithm or Bellman-Ford's Algorithm are used to find the shortest path between two locations.
Recommended Knowledge
- Graph Theory
- Dijkstra's Algorithm
- Path Finding Algorithms
- Directed Graph
- Weighted Graph
- Priority Queue
- Adjacency List
- Hash Map
What do we know?
- We're given an array [
flights
] whereflights[i]
=[from, to, price]
indicates that there is a flight from cityfrom
tocity
to
with costprice
. Which can be represented as a Adjacency List. - We need to go from
src
todst
withink
stops. Where we're looking for the cheapest flight betweensrc
anddst
withink
stops.
How we're going to do it:
We're going to use Dijkstra's Algorithm to find the shortest path between src
and dst
where we start from the cheapest flights relative to src
in ascending order until we reach dst
or we reach k
stops. Once we reach the dst
we can return the the cost of the flight relative to src
.
The most important part to note here, is that we need to prevent ourself from going to the same city multiple times. So we use a [Hashmap] to keep track of the number of stops it took to visit that city the first time, so we can see if it's worth revisiting that city on a different path again.
- We're going to create a
Priority Queue
to hold all the nodes that we need to traverse. As in Dijkstra's Algorithm, we're going to use aPriority Queue
to hold the nodes that we need to traverse first. (Cheapest flight first) - We're also going to keep a global hashmap to see if we've visited that city before and if we have how many stops it took to get to that city, it lets us know in the future if we should revisit that city. Meaning, that it's cheaper than our current node and we're good to go back here.
- As we know we're starting at
src
, we're going to add it to thePriority Queue
with a value of 0, because it cost us nothing as we started here and 0 stops too. - We will then begin performing Dijkstra's Algorithm, where we remove the 'cheapest' item from the Min-Heap, meaning we brute force all the cheapest flights first so long as it's within
k
stops. We will also register the number of stops it took to get to that city in that Set. - We're then going to continually explore the cheapest flights and add them to the
Priority Queue
until we reachdst
or we reachk
stops.
Big O Notation:
- Time Complexity: O(((V + E) * K)) | Right so this is a little confusing. Dijkstra's Algorithm is a O(ElogV) algorithm. Where E is the number of edges in the graph and V is the number of vertices in the graph. Which is represented by O(V^2), as in the worst case, every node and it's neighbors will be added and removed from the Min-Heap multiple times. But as we're limited by K, we're going to limit ourself to K stops, so we're going to limit ourself to K * V * E operations. So in it's amortized form, it's O((V + E) * K). In worst case, we can represent it as O((V^2)).
- Space Complexity: O(V + E) | As in the worst case, we're going to store the entire graph within our Min-Heap or our visited set.
Is my analysis wrong? Potentially, feel free to correct me. π
Leetcode Results:
The Solution
const findCheapestPrice = function (n, flights, src, dst, K) {
// Firstly build an Adjacency List
// City => [[Out-City, Cost], [Out-City, Cost], ...]
const node_edge_cost = new Map();
for (const [from, to, price] of flights){
let edges = [];
if (node_edge_cost.has(from)){
edges = node_edge_cost.get(from);
}
edges.push([to, price])
node_edge_cost.set(from, edges)
}
// Dijkstra's Algorithm in this case uses a min-heap to store the cheapest paths.
const min_heap = new MinPriorityQueue();
// We also have a distance from K memo.
// As it's entirely possible to revisit a node again, so it's useful to
// know it's distance from K. So we can know if it's worth even visiting it.
const distance_from_k_memo = new Map();
// We want to start of with the provided source node.
// It's distance from DST is set to the maximum value it
// can possibly be, that being K. As we don't want to
// to visit a node that's too far away. So we use K to dictate that distance.
// So once, we branch out and get to 0, and not reached K, we'll stop.
min_heap.enqueue([src, K + 1], 0);
// Keep running Dijkstra's Algorithm until we've reached the destination.
// Or the min-heap is empty.
while (min_heap.size()){
// Get the cheapest path from the min-heap.
// Get the price of the cheapest path.
// And get the city and distance from DST
const node = min_heap.dequeue();
const price = node.priority;
const [to, distance_from_k] = node.element;
// Set it within the memo, just in case
// we come across this node again in the future.
// So we can tell if it's worth even visiting it again.
distance_from_k_memo.set(to, distance_from_k);
// We've reached the cheapest path to the destination.
// Return the price.
if (to === dst) return price;
// Hmm, seems like we're 0 distance from the destination / K.
// but not at the destination, guess it's time to backtrack.
if (distance_from_k <= 0) continue;
// Get the outbound edges from the current node.
const edges = node_edge_cost.get(to) || [];
// Go through each edge and enqueue it.
// So long as it's worth visiting (Meaning, that if we've visited it, is it
// cheaper than the current cheapest path?) If so we can add it back into the min-heap.
for (const [outbound, out_cost] of edges){
if (distance_from_k_memo.get(outbound) >= distance_from_k - 1) continue;
// Enqueue into the min heap with updated cost and distance from K.
min_heap.enqueue([outbound, distance_from_k - 1], out_cost + price)
}
}
// This is embarrassing, but we've reached the end of the graph
// and not found DST within K hops. So we return -1.
return -1;
};
Top comments (0)