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 signal starts at node 2. It takes 1 unit time to reach node 1 and node 3. Then it takes 2 units time to reach node 4. So the minimum time for all nodes to receive the signal is 2.

Example 2

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

Output: 1

Explanation: The signal starts at node 1. It takes 1 unit time to reach node 2.

Steps

1. Build the graph: Represent the network as an adjacency list. Each node will have a list of its neighbors and the corresponding edge weights.
2. Initialize distances: Create a distance array dist of size n+1, where dist[i] represents the minimum time to reach node i from node k. Initialize all distances to infinity (a large value) except for dist[k] = 0.
3. Dijkstra's Algorithm: Use Dijkstra's algorithm to find the shortest paths from node k to all other nodes. Dijkstra's algorithm iteratively selects the node with the minimum distance and updates the distances of its neighbors.
4. Check for unreachable nodes: After Dijkstra's algorithm completes, check if any node has an infinite distance. If so, it means that node is unreachable from k, and we return -1.
5. Find the maximum distance: Otherwise, find the maximum distance among all nodes. This represents the minimum time it takes for all nodes to receive the signal.

Explanation

Dijkstra's algorithm is a greedy algorithm that finds the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights. It works by maintaining a set of visited nodes and a priority queue (in this case, a min-heap) of unvisited nodes ordered by their distances from the source. In each iteration, it selects the node with the minimum distance from the priority queue, marks it as visited, and updates the distances of its unvisited neighbors.

The adjacency list representation is efficient for accessing neighbors of a node.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int NetworkDelayTime(int[][] times, int n, int k) {
        // Build the graph (adjacency list)
        List<Tuple<int, int>>[] graph = new List<Tuple<int, int>>[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new List<Tuple<int, int>>();
        }
        foreach (int[] time in times) {
            graph[time[0]].Add(new Tuple<int, int>(time[1], time[2]));
        }

        // Initialize distances
        int[] dist = new int[n + 1];
        Array.Fill(dist, int.MaxValue);
        dist[k] = 0;

        // Dijkstra's algorithm
        PriorityQueue<Tuple<int, int>> pq = new PriorityQueue<Tuple<int, int>>(); // (distance, node)
        pq.Enqueue(new Tuple<int, int>(0, k));

        while (pq.Count > 0) {
            Tuple<int, int> current = pq.Dequeue();
            int u = current.Item2;
            int d = current.Item1;

            if (d > dist[u]) continue; //Optimization: Skip if a shorter path already exists

            foreach (Tuple<int, int> edge in graph[u]) {
                int v = edge.Item1;
                int weight = edge.Item2;
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.Enqueue(new Tuple<int, int>(dist[v], v));
                }
            }
        }

        // Check for unreachable nodes and find the maximum distance
        int maxDist = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == int.MaxValue) return -1;
            maxDist = Math.Max(maxDist, dist[i]);
        }

        return maxDist;
    }
}


//PriorityQueue implementation (if not available in your C# version)
public class PriorityQueue<T> where T : IComparable<T>
{
    private List<T> data = new List<T>();

    public void Enqueue(T item)
    {
        data.Add(item);
        int index = data.Count - 1;
        while (index > 0)
        {
            int parentIndex = (index - 1) / 2;
            if (data[index].CompareTo(data[parentIndex]) < 0)
            {
                Swap(index, parentIndex);
                index = parentIndex;
            }
            else
            {
                break;
            }
        }
    }

    public T Dequeue()
    {
        if (data.Count == 0) throw new Exception("Queue is empty");
        T result = data[0];
        data[0] = data[data.Count - 1];
        data.RemoveAt(data.Count - 1);
        int index = 0;
        while (true)
        {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;
            int smallestIndex = index;
            if (leftChildIndex < data.Count && data[leftChildIndex].CompareTo(data[smallestIndex]) < 0)
            {
                smallestIndex = leftChildIndex;
            }
            if (rightChildIndex < data.Count && data[rightChildIndex].CompareTo(data[smallestIndex]) < 0)
            {
                smallestIndex = rightChildIndex;
            }
            if (smallestIndex != index)
            {
                Swap(index, smallestIndex);
                index = smallestIndex;
            }
            else
            {
                break;
            }
        }
        return result;
    }

    public int Count => data.Count;
    private void Swap(int i, int j)
    {
        T temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

Complexity

• Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices (nodes). This is the time complexity of Dijkstra's algorithm using a priority queue.
• Space Complexity: O(V + E), due to the adjacency list and the distance array. The priority queue also adds to space complexity, but its size is at most V in the worst case.