Network Delay Time — Dijkstra Shortest Paths

Problem

There are n nodes. A signal is sent from k. With directed weighted edges, find time for all nodes to receive signal, or -1 if impossible.

Approach — Dijkstra

Single-source shortest path from k. Answer = max(dist.values()), or -1 if some unreachable.

Time: O(E log V) | Space: O(V+E)

Solutions

Python

import heapq
from collections import defaultdict
class Solution:
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        adj=defaultdict(list)
        for u,v,w in times: adj[u].append((v,w))
        dist={i:float('inf') for i in range(1,n+1)}; dist[k]=0
        heap=[(0,k)]
        while heap:
            d,u=heapq.heappop(heap)
            if d>dist[u]: continue
            for v,w in adj[u]:
                if dist[u]+w<dist[v]:
                    dist[v]=dist[u]+w; heapq.heappush(heap,(dist[v],v))
        ans=max(dist.values())
        return ans if ans<float('inf') else -1

C++

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k){
        vector<vector<pair<int,int>>> adj(n+1);
        for(auto& t:times) adj[t[0]].push_back({t[1],t[2]});
        vector<int> dist(n+1,INT_MAX); dist[k]=0;
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
        pq.push({0,k});
        while(!pq.empty()){
            auto[d,u]=pq.top();pq.pop();
            if(d>dist[u]) continue;
            for(auto[v,w]:adj[u])
                if(dist[u]+w<dist[v]){dist[v]=dist[u]+w;pq.push({dist[v],v});}
        }
        int ans=*max_element(dist.begin()+1,dist.end());
        return ans==INT_MAX?-1:ans;
    }
};

Complexity

Time: O(E log V) | Space: O(V+E)