> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/graph/network-delay-time.md).

# Network Delay Time

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

We will send a signal from a given node `k`. Return *the **minimum** 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`.

 

**Example 1:**

![](https://assets.leetcode.com/uploads/2019/05/23/931_example_1.png)

<pre><code><strong>Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
</strong><strong>Output: 2
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: times = [[1,2,1]], n = 2, k = 1
</strong><strong>Output: 1
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: times = [[1,2,1]], n = 2, k = 2
</strong><strong>Output: -1
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= k <= n <= 100`
* `1 <= times.length <= 6000`
* `times[i].length == 3`
* `1 <= ui, vi <= n`
* `ui != vi`
* `0 <= wi <= 100`
* All the pairs `(ui, vi)` are **unique**. (i.e., no multiple edges.)

### Solutions

This problem can be solved using Dijkstra’s algorithm, which is a famous algorithm for finding the shortest paths from a single source in a graph with non-negative edge weights.

```csharp
public class Solution {
    public int NetworkDelayTime(int[][] times, int n, int k) {
        var graph = new Dictionary<int, List<(int, int)>>();
        foreach (var time in times) {
            if (!graph.ContainsKey(time[0])) {
                graph[time[0]] = new List<(int, int)>();
            }
            graph[time[0]].Add((time[1], time[2]));
        }

        var dist = new Dictionary<int, int>();
        for (int i = 1; i <= n; ++i) {
            dist[i] = int.MaxValue;
        }
        dist[k] = 0;

        var heap = new SortedSet<(int, int)>() { (0, k) };
        while (heap.Count > 0) {
            var node = heap.Min;
            heap.Remove(node);
            int d = node.Item1, nodeIdx = node.Item2;
            if (d != dist[nodeIdx]) continue;
            if (graph.ContainsKey(nodeIdx)) {
                foreach (var pair in graph[nodeIdx]) {
                    int nei = pair.Item1, d2 = pair.Item2;
                    if (dist[nodeIdx] + d2 < dist[nei]) {
                        heap.Remove((dist[nei], nei));
                        dist[nei] = dist[nodeIdx] + d2;
                        heap.Add((dist[nei], nei));
                    }
                }
            }
        }

        int ans = 0;
        foreach (var cand in dist) {
            ans = Math.Max(ans, cand.Value);
        }
        return ans == int.MaxValue ? -1 : ans;
    }
}
```

The time complexity of this solution is O(E log E), where E is the number of edges (or the length of times), because in the worst case we need to iterate over each edge and update the queue. The space complexity is O(N + E), where N is the number of nodes, because we need to store the graph (O(E)) and the distance of each node (O(N)).