algoadvance

Leetcode 743. Network Delay Time

Problem Statement

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] = (u_i, v_i, w_i), where u_i is the source node, v_i is the target node, and w_i is the time it takes for a signal to travel from source to target.

We need to send a signal from a given node k. Return the 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.

Clarifying Questions

  1. Can there be multiple edges between the same nodes?
    • Typically, no, but if there are, choose the edge with the minimum weight.
  2. Can the signal path form cycles?
    • Yes, cycles can form in the graph.
  3. Are the weights of the edges (time) always positive?
    • Yes, the problem states travel times, so they are positive integers.
  4. Will the given node k always be valid (within 1 to n)?
    • Yes, 1 <= k <= n.

Strategy

We will model this problem using Dijkstra’s algorithm, which is suitable for finding the shortest path in a graph with edge weights.

  1. Graph Representation: Represent the graph using an adjacency list. Each node will have a list of tuples representing the target node and the weight of the edge.

  2. Min-Heap: Use a priority queue (min-heap) to always expand the least cost edge.

  3. Distance Array: Maintain an array to track the minimum distance to each node. Initialize the distance to the starting node k to 0 and all other nodes to infinity.

  4. Priority Queue Initialization: Start the priority queue with the starting node k with distance 0.

  5. Dijkstra’s Algorithm Execution:
    • While the priority queue is not empty, extract the minimum distance element.
    • Update the distances for its adjacent nodes if a shorter path is found.
    • Add the updated nodes to the priority queue for further exploration.
  6. Result Calculation: If all nodes are reachable, the time for the signal to reach the farthest node is the answer. Otherwise, return -1.

Code

#include <vector>
#include <queue>
#include <utility>
#include <unordered_map>
#include <algorithm>
#include <climits>

using namespace std;

int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    // Graph representation
    unordered_map<int, vector<pair<int, int>>> graph;
    for (const auto& edge : times) {
        int u = edge[0], v = edge[1], w = edge[2];
        graph[u].emplace_back(v, w);
    }
    
    // Distance array
    vector<int> dist(n + 1, INT_MAX);
    dist[k] = 0;
    
    // Min-heap priority queue
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.emplace(0, k);
    
    while (!pq.empty()) {
        auto [current_dist, u] = pq.top();
        pq.pop();
        
        if (current_dist > dist[u]) {
            continue;
        }
        
        for (const auto& [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    
    // Calculate the result
    int max_delay = *max_element(dist.begin() + 1, dist.end());
    return max_delay == INT_MAX ? -1 : max_delay;
}

Time Complexity

Thus, the overall time complexity is O((E + V) log V).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI