Solution Developed In:

The Question

For this article we will be covering Leetcode's '743. 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.

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 or Bellman-Ford's 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 in a Graph. For me I found this question impossible to solve until I read up that it was solved by Dijkstra's 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, except we're not creating a Minimum Spanning Tree but a Shortest Path between k and all the other nodes.

How do you think Google Maps knows the shortest distance between your house and your friend's house? Shortest Path algorithms like Dijkstra's Algorithm or Bellman-Ford's 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
2. Dijkstra's Algorithm
3. Hashmap
4. Adjacent List
5. Path Finding Algorithms
6. Priority Queue
7. Heap

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 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 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 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 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 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:

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