18.Network Delay Time

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2

Solution: (Dijkstra Algorithm)

class Solution
{
public:
    void findSortestPath(vector<pair<int, int>> v[], vector<int> &dist, int src)
    {

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, src});
        dist[src] = 0;

        while (!pq.empty())
        {

            pair<int, int> p = pq.top();
            pq.pop();

            int node = p.second;

            for (auto itr = v[node].begin(); itr != v[node].end(); itr++)
            {

                int x = (*itr).first;
                int w = (*itr).second;

                if (dist[node] + w < dist[x])
                {
                    dist[x] = w + dist[node];
                    pq.push({dist[x], x});
                }
            }
        }
        return;
    }

    int networkDelayTime(vector<vector<int>> &times, int n, int K)
    {

        vector<pair<int, int>> v[n + 1];
        for (int i = 0; i < times.size(); i++)
        {
            v[times[i][0]].push_back({times[i][1], times[i][2]});
        }

        vector<int> dist(n+1, INT_MAX);
        findSortestPath(v, dist, K);

        int maxDist = INT_MIN;
        for (int i = 1; i <= n; i++)
        {
            if (dist[i] > maxDist)
            {
                maxDist = dist[i];
            }
        }
        
        if(maxDist == INT_MAX){
            return -1;
        }
        
        return maxDist;
    }
};

Time Complexity:- O(V + E logV) in the heap implementation (Priority Queue)