Network Delay Time medium

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 (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. Your task is to find the minimum time it takes for all the n 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

Explanation: The graph looks like this:

2 --> 1 (1 unit time)
2 --> 3 (1 unit time)
3 --> 4 (1 unit time)

The minimum time to reach all nodes from node 2 is 2 (2->3->4).

Example 2

Input: times = [[1,2,1]], n = 2, k = 1 Output: 1

Explanation: The graph looks like this:

1 --> 2 (1 unit time)

The minimum time to reach all nodes from node 1 is 1.

Steps

1. Represent the graph: Use an adjacency list to represent the directed graph. The adjacency list will store the destination nodes and the weights of the edges for each source node.

2. Dijkstra's Algorithm: Use Dijkstra's algorithm to find the shortest path from the starting node k to all other nodes. Dijkstra's is ideal because it efficiently finds the shortest paths in a graph with non-negative edge weights.

3. Distance Array: Initialize a distance array dist of size n+1 (to account for 1-based indexing) with INT_MAX for all nodes except the starting node k, which is initialized to 0.

4. Min Heap (Priority Queue): Use a min-heap (priority queue) to efficiently retrieve the node with the smallest distance.

5. Iteration: Iterate until the min-heap is empty. In each iteration:

   • Extract the node u with the smallest distance from the min-heap.
   • Iterate through its neighbors.
   • If a shorter path to a neighbor v is found ( dist[u] + weight < dist[v]), update dist[v] and add v to the min-heap.

6. Maximum Distance: After Dijkstra's algorithm completes, find the maximum distance among all nodes. This represents the time it takes to reach the furthest node.

7. Check for Unreachable Nodes: If any node's distance remains INT_MAX after the algorithm, it means it's unreachable from k, and we return -1.

Explanation

Dijkstra's algorithm systematically explores the graph, always choosing the node with the shortest known distance from the source. The min-heap ensures that we efficiently select the next node to explore. The algorithm guarantees finding the shortest paths from the source node to all other reachable nodes.

Code

#include <iostream>
#include <vector>
#include <limits> // for numeric_limits
#include <queue>

using namespace std;

int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    // Adjacency list representation of the graph
    vector<vector<pair<int, int>>> graph(n + 1);
    for (const auto& time : times) {
        graph[time[0]].push_back({time[1], time[2]});
    }

    // Initialize distances to infinity except for the starting node
    vector<int> dist(n + 1, numeric_limits<int>::max());
    dist[k] = 0;

    // Min-heap (priority queue)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, k});

    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        // If the current distance is greater than the stored distance, skip
        if (d > dist[u]) continue;

        // Explore neighbors
        for (const auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    // Find the maximum distance and check for unreachable nodes
    int maxDist = 0;
    for (int i = 1; i <= n; ++i) {
        if (dist[i] == numeric_limits<int>::max()) return -1; // Unreachable node
        maxDist = max(maxDist, dist[i]);
    }

    return maxDist;
}

int main() {
    vector<vector<int>> times1 = {{2, 1, 1}, {2, 3, 1}, {3, 4, 1}};
    int n1 = 4, k1 = 2;
    cout << "Example 1: " << networkDelayTime(times1, n1, k1) << endl; // Output: 2

    vector<vector<int>> times2 = {{1, 2, 1}};
    int n2 = 2, k2 = 1;
    cout << "Example 2: " << networkDelayTime(times2, n2, k2) << endl; // Output: 1

    return 0;
}

Complexity

• Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices (nodes). This is dominated by Dijkstra's algorithm using a min-heap.
• Space Complexity: O(V + E) due to the adjacency list and the distance array. The priority queue also takes space proportional to the number of edges in the worst case.