787. Cheapest Flights Within K Stops 🚀
Tags: javascript, programming, webdev, leetcode
Published: 2022-07-27 13:38:45

***
### Solution Developed In:
![JavaScript](https://img.shields.io/badge/javascript-%23323330.svg?style=for-the-badge&logo=javascript&logoColor=%23F7DF1E)

## The Question
For this article we will be covering Leetcode's '[787. Cheapest Flights Within K Stops](https://leetcode.com/problems/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 `from `to `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`.

![Example](https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-3drawio.png)

![Example](https://assets.leetcode.com/users/images/a6d0e23a-316e-44b5-8ff9-0107698dd8a4_1658324375.6277692.gif)


```
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](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) or [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra's_algorithm) 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](https://en.wikipedia.org/wiki/Dijkstra's_algorithm) and **medium** if using [Bellman-Ford](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm). For this question, we're going to use [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra's_algorithm) to solve it.

[Dijkstra](https://en.wikipedia.org/wiki/Dijkstra's_algorithm) is a greedy algorithm that finds the shortest path from a source to a destination. It works a lot like [Breadth First Search](https://en.wikipedia.org/wiki/Breadth-first_search). We're going to explore the cheapest flights from `src` to `dst` within `k` stops.

How do you think [Google Maps](https://www.google.com/maps) knows the shortest distance (Be distance or cost) between your house and New Yorks Airport? [Shortest Path](https://en.wikipedia.org/wiki/Shortest_path) algorithms like [Dijkstra's Algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) or [Bellman-Ford's Algorithm](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) are used to find the shortest path between two locations. 

***

##  Recommended Knowledge
1. [Graph Theory](https://en.wikipedia.org/wiki/Graph_theory#:~:text=In%20mathematics%2C%20graph%20theory%20is,also%20called%20links%20or%20lines)
2. [Dijkstra's Algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)
4. [Path Finding Algorithms](https://en.wikipedia.org/wiki/Path_finding_algorithm)
5. [Directed Graph](https://en.wikipedia.org/wiki/Directed_graph)
6. [Weighted Graph](https://en.wikipedia.org/wiki/Weighted_graph)
7. [Priority Queue](https://en.wikipedia.org/wiki/Priority_queue)
8. [Adjacency List](https://en.wikipedia.org/wiki/Adjacency_list)
9. [Hash Map](https://en.wikipedia.org/wiki/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 `from `to `city` `to` with cost `price`. Which can be represented as a [Adjacency List](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Dijkstra%27s_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](https://en.wikipedia.org/wiki/Dijkstra%27s_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](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm), where we remove the 'cheapest' item from the [Min-Heap](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Dijkstra%27s_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](https://en.wikipedia.org/wiki/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: 
[![LeetCode](https://img.shields.io/badge/LeetCode-000000?style=for-the-badge&logo=LeetCode&logoColor=#d16c06)](https://leetcode.com/submissions/detail/757580590/)


***
<!-- <iframe src="https://leetcode.com/playground/8NQd4XgG/shared" frameBorder="0" width="100%" height="300"></iframe> -->

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