[Algorithms] 13 - Network Delay Time

1. Overview

• The problem needs understanding of Djikstra's shortest path algorithm.

• The problem needs understanding of min-heap.

• The problem needs understanding of adjacency matrix.

• The problem needs understanding of Breadth-First-Search (BFS)

2. Solution

The solution is not very complicated, since the algorithm(Djisktra's shortest path) is a greedy algorithm.

The first big hint we can consider to approach this problem would be that each node can have connected nodes as many as it wants. Therefore, we need an adjacency matrix to keep track of how many nodes are connected to each node. Notice that each node will be stored in 2D array as a pair since each node has different weight(time) to reach.

C++ example

// time will be given as => vector<vector<int>>& times;
vector<vector<pair<int, int>>> adj(n+1);
for(auto t : times)
{
     int source = t[0];
     int dest = t[1];
     int time = t[2];

     // From 'source', we can reach 'dest' consuming 'time'
     adj[source].push_back({time, dest});
}

Moreover, note that we need to since we have the starting node K, and we need to scan the nodes in level order. We need the level order scan because we are interested in finding the shortest amount of time elapsed to reach each node from K. And that can be done by scanning all nodes attached to the current node (level order). And level order search can be done by implementing BFS.

BFS will be implemented using a queue. But for this specific problem, we need a priority queue (min-heap). Why would we use priority queue? Since the algorithm is greedy, we want to test the node with the shortest elapsed time FIRST. So any node that has smallest accumulated time will have the first priority.

We also need an array that can keep track of the previous smallest accumulated time it took to get to the ith node. This will be used to return the result.

C++ Example

// There are going to be n number of nodes
// recvTimes[i] : Minimum time it takes to reach i from K
vector<int> recvTimes(n + 1, INT_MAX);

// K from K will take 0
recvTimes[k] = 0;

3. Full Implementation

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {

        // 0: weight
        // 1: destination
        vector<vector<pair<int, int>>> adj(n+1);

        for(auto t : times)
        {
            int source = t[0];
            int dest = t[1];
            int time = t[2];
            adj[source].push_back({time, dest});
        }

        // Keep track of minimum time of receiving signal from node k
        vector<int> recvTimes(n + 1, INT_MAX);
        recvTimes[k] = 0;

        // Minheap
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0,k});

        while(!pq.empty())
        {
            // Getting the current node (pair).
            int currNode = pq.top().second;
            int currTime = pq.top().first;
            pq.pop();

            // Skip if the pair cannot be an optimal solution
            if (currTime > recvTimes[currNode]) 
                continue;

            // Scan all attached nodes and push to pq if the item can be an optimal solution.
            // Don't forget to update the elapsed time.
            for(auto item : adj[currNode]){
                if(recvTimes[item.second] > currTime+item.first){
                    recvTimes[item.second] = currTime+item.first;
                    pq.push({currTime+item.first, item.second});
                }
            }

        }

        int result = INT_MIN;

        // Getting results
        for (int i = 1; i <= n; i++){
            result = max(recvTimes[i], result);
        }

        return (result==INT_MAX) ? -1 : result;
    }
};