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 of flights. You are given an array flights where flights[i] = [fromi, toi, pricei]indicates that there is a flight from city fromto city to with cost price.

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.

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

1. Graph Theory
2. Dijkstra's Algorithm
3. Path Finding Algorithms
4. Directed Graph
5. Weighted Graph
6. Priority Queue
7. Adjacency List
8. Hash Map

What do we know?

1. We're given an array [flights] where flights[i] = [from, to, price]indicates that there is a flight from city fromto city to with cost price. Which can be represented as a Adjacency List.
2. We need to go from src to dst within k stops. Where we're looking for the cheapest flight between src and dst within k 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.

1. 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 a Priority Queue to hold the nodes that we need to traverse first. (Cheapest flight first)
2. 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.
3. As we know we're starting at src, we're going to add it to the Priority Queue with a value of 0, because it cost us nothing as we started here and 0 stops too.
4. 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.
5. We're then going to continually explore the cheapest flights and add them to the Priority Queue until we reach dst or we reach k 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:

See Submission Link:

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;
};