743. Network Delay Time 🚀
Tags: javascript, programming, tutorial, showdev
Published: 2022-07-19 16:20:23

***
### 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 '[743. Network Delay Time](https://leetcode.com/problems/network-delay-time/)' question. An Advanced Graph question. 

Question:

> You are given a network of `n` nodes, labeled from `1` to `n`. You are also given times, a list of travel `times` as directed edges `times[i] = (ui, vi, wi),` where `ui` is the source **node**, `vi` is the target node, and `wi` is the time it takes for a signal to travel from source to target.
> We will send a **signal** from a given node `k`. Return the minimum time it takes for all the `n` nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return `-1`.

![Example](https://assets.leetcode.com/uploads/2019/05/23/931_example_1.png)


```
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
```

## Explaining The Question
This Question is rated **Medium**. Which is I would say is accurate if you're familiar with [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) or any other path finding algorithm. Most people will study this algorithm in Higher Education. But if you're like me, not having attending higher education mean't I hadn't the slightest clue about [Path Finding Algorithms](https://en.wikipedia.org/wiki/Path_finding_algorithm) in a Graph. For me I found this question impossible to solve until I read up that it was solved by [Dijkstra's Algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm).

We're given a graph and we're asked to to traverse the entire graph and hit all nodes using the shortest path. Which sounds a lot like [Kruskal's Algorithm](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm), except we're not creating a [Minimum Spanning Tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree) but a [Shortest Path](https://en.wikipedia.org/wiki/Shortest_path) between `k` and all the other nodes.

How do you think [Google Maps](https://www.google.com/maps) knows the shortest distance between your house and your friend's house? [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. 

Which is exactly what we're going to do. Finding the shortest path between `k` and all the other nodes.

***

##  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)
3. [Hashmap](https://www.w3schools.com/jsref/jsref_obj_hash.asp)
4. [Adjacent List](https://www.w3schools.com/jsref/jsref_obj_array.asp)
5. [Path Finding Algorithms](https://en.wikipedia.org/wiki/Path_finding_algorithm)
6. [Priority Queue](https://en.wikipedia.org/wiki/Priority_queue)
7. [Heap](https://en.wikipedia.org/wiki/Heap_(data_structure))

## What do we know?
1. We're given an list of Nodes with a connection and it's cost.
2. It's possible for a node to not have any inbound connections, and so in this case, we must return -1 as it would be impossible to reach all nodes from {k}

## 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 `k` and all the other nodes.

Firstly, we will generate ourselves a Adjacent List (Node -> [Edge, Cost]). We do this so we know all the connection ands costs in the graph. From here, we generate a empty [Minumum Priority Queue](https://en.wikipedia.org/wiki/Priority_queue) and we add the first node to the queue at the cost of 0, as we start here.

We will then, use a while loop to keep looping until the queue is empty, where we will pop off the min-heap which will always give us the next shortest possible path. With this node, we will then keep adding that new nodes edges to the [min-heap](https://en.wikipedia.org/wiki/Min-heap) and update the cost of the node. 

The reason we update the cost of the node is because we're moving out relative to {k}, out input node. Meaning the shortest path cascades outwards from {k}. We keep adding the shortest path to the node and it's edges to the min-heap until we've visited all nodes within the graph. We know we've visited all nodes because we use a [Set](https://www.w3schools.com/jsref/jsref_obj_set.asp) to keep track of which nodes we've visited. 

Each time we move a node, we update the global time variable. Where if the time has increased relative to {k} we increase it by the cost of the edge.

## Big O Notation:
* Time Complexity:   *O(**V^2**)* | As it is entirely possible for each vertex to be connected to every other vertex. Thus, we could potentially visit every vertex multiple times. Although our set makes sure they don't process it. 

* Space Complexity: *O(**V^2**)* | As we're going to store the operations within a heap.

The Time and Space complexities of [Dijkstra's Algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) are very very confusing so feel free to correct my anlysis of Dijkstra's Algorithm using a Min-heap for this specific quesiton. When figuring out the complexity I imagined a graph where every node is connected to every node except itself. 
## 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/750518834/)


***

# The Solution
```
/**
 * @param {number[][]} times
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var networkDelayTime = function (times, n, k) {

    
    // Our return value, how long did it take
    // to reach all nodes within the network from {k}
    let time_taken = 0;

    // A set so we don't visit the same node twice.
    const visited_set = new Set();

    // A min heap, as we want to visit the the node
    // with the cheapest path so far. Relative to {k}.
    // See: https://github.com/datastructures-js/priority-queue
    // Heaps are built into Leetcodes Runtime for JavaScript. 😁😁
    const min_heap = new MinPriorityQueue();

    // An adjacency list, where we store 
    // Node -> [[Edge, Cost],[Edge, Cost]]
    const node_edge_cost = new Map();

    // Build the adjacency list.
    for (const [node, edge, cost] of times) {
        let edges = [];
        if (node_edge_cost.has(node)) {
            edges = node_edge_cost.get(node);
        }
        edges.push([edge, cost]);
        node_edge_cost.set(node, edges);
    }

    // We have been asked to start at {k}
    // So we enqueue {k} at the cost of 0, as of course
    // it costs nothing as we start here.
    min_heap.enqueue([k, 0], 0);

    // Perform Dijkstra's algorithm.
    // Get the cheapest operation relative to {k}
    // and add it's edges to the heap, where we're always
    // updating the cost relative to {k}. Therefore, 
    // we're visiting all the cheapest operations relative to {k}.
    while (min_heap.size()) {

        // Get the cheapest operation relative to {k}
        // Node and cost
        const [node, cost] = min_heap.dequeue().element;

        // Have we already been here? No loops today kiddo
        if (visited_set.has(node)) continue;

        // Set it. We don't want to come back here. 
        visited_set.add(node);

        // Did our distance increase?
        // If so, update it. If not, keep the same
        time_taken = Math.max(cost, time_taken);

        // Get the edges for this node (If any)
        const node_edges = node_edge_cost.get(node) || [];

        // Get all the edges for this node and add them to the heap
        // If they haven't been visited yet. Note:
        // We're adding the cost of the given nde to the cost of the edge.
        // Because we're moving out relative to {k}. Thus,
        // even if all nodes have a cost of 2.
        // It's going to cascade outwards.
        // 2 -> 4 -> 6 -> 8 etc.
        for (const [edge_node, edge_cost] of node_edges) {
            if (!visited_set.has(edge_node)) {
                
                // Add it to the queue, set the priority to the cost of the edge
                // So we only ever visit the cheapest edge.
                min_heap.enqueue([edge_node, edge_cost + cost], edge_cost + cost);
            }
        }
    }

    // Did we visit every node?
    // If not, we failed to spread the message across the network.
    // If so, return the time taken. 
    return visited_set.size === n ? time_taken : -1;
};

```