# 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)).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://docs-57.gitbook.io/data-structure-and-algorithms/problems/graph/network-delay-time.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.