## DEV Community

Samuel Hinchliffe 🚀

Posted on

# 743. Network Delay Time 🚀

## 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.

## 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.

# 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();

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.

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

``````