743. Network Delay Time

📝 Problem Details

• Title: 743. Network Delay Time
• Link: https://leetcode.com/problems/network-delay-time/
• Difficulty: Medium
• Tags/Categories: Graphs Dijkstras-Shortest-Path

input integer n dictating the number of nodes from 1 to n input vector times which are a list of travel times these should be treated as directed edges times[i] = (ui, vi, wi) u --> source node v --> destination node w --> weight of edge (time it takes to go from source to destination) input integer k representing a signal starting from a specific node return the minimum time it takes for all n nodes to receive the signal if its impossible return -1

💭What Were My Initial Thoughts?

- we need to find the shortest path from node k to all n nodes
- the weights of the edges are positive
- all pairs are unique
- this fits djikstras shortest path
- if any node is unreachable return -1

💡 Explanation of Solution

1. graph representation
	- input array times represents a weighted directed graph
	- convert this into an adjacency list 
	- (unordered_map<int, vector<pair<int, int>>>) where:
	- graph[u] = {(v1, w1), (v2, w2), ...} means there is an edge from u to v1, v2 with weights w1, w2

2. dijkstra's algorithm
	 - use a min heap to always process the shortest known path first
	 - start from ndoe k with distance 0
	 - keep expanding to the shortest reachable nodes until all nodes are visited
	 - if any node remains unreachable, return -1

⌛ Complexity Analysis

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

💻 Implementation of Solution

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        
        // build adjacency list representation of the graph
        unordered_map<int, vector<pair<int,int>>> graph;
        for(const auto& edge : times) {
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];
            graph[u].push_back({v,weight}); // directed edge u --> v with weight w
        }
 
        // min heap priority queue for djikstras
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> minHeap;
        minHeap.push({0,k}); // {time, node} - start node k with time 0
 
        // initalise all nodes with infinity (unreachable)
        unordered_map<int, int> minTime;
        for(int i = 1; i <= n; i++){
            minTime[i] = INT_MAX;
        }
        minTime[k] = 0; // distance to itself is 0
 
        // process nodes in order of shortest time first 
        while(!minHeap.empty()) {
            auto[time, node] = minHeap.top();
            minHeap.pop();
 
            // skip if we already found a shorter path before
            if(time > minTime[node]) continue;
 
            // explore all neighbours of current node
            for(auto [neighbour, travelTime] : graph[node]) {
                int newTime = time + travelTime;
                if(newTime < minTime[neighbour]) {
                    minTime[neighbour] = newTime; // update shortest path to neighbour
                    minHeap.push({newTime, neighbour}); // push to pq
                }
            }
        }
 
        // find the lognest time among all reachable nodes
        int maxTime = 0;
        for(const auto& [node, time] : minTime) {
            if(time == INT_MAX) return -1; // some nodes are unreachable from node k
            maxTime = max(maxTime, time);
        }
 
        return maxTime;
    }
};