This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

There are `N`

network nodes, labelled `1`

to `N`

.

Given `times`

, a list of travel times as **directed** edges `times[i] = (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`

. How long will it take for all nodes to receive the signal? If it is impossible, return `-1`

.

**Note:**

`N`

will be in the range`[1, 100]`

.`K`

will be in the range`[1, N]`

.- The length of
`times`

will be in the range`[1, 6000]`

. - All edges
`times[i] = (u, v, w)`

will have`1 <= u, v <= N`

and`1 <= w <= 100`

.

b'

\n\n#### Approach #1: Depth-First Search [Accepted]

\n

\n#### Approach #2: Dijkstra\'s Algorithm [Accepted]

\n

\n

'
**Intuition**

Let\'s record the time `dist[node]`

when the signal reaches the node. If some signal arrived earlier, we don\'t need to broadcast it anymore. Otherwise, we should broadcast the signal.

**Algorithm**

We\'ll maintain `dist[node]`

, the earliest that we arrived at each `node`

. When visiting a `node`

while `elapsed`

time has elapsed, if this is the currently-fastest signal at this node, let\'s broadcast signals from this node.

To speed things up, at each visited node we\'ll consider signals exiting the node that are faster first, by sorting the edges.

\n\n**Complexity Analysis**

- \n
- \n
Time Complexity: where is the length of

\n`times`

. We can only fully visit each node up to times, one per each other node. Plus, we have to explore every edge and sort them. Sorting each small bucket of outgoing edges is bounded by sorting all of them, because of repeated use of the inequality . \n - \n
Space Complexity: , the size of the graph (), plus the size of the implicit call stack in our DFS ().

\n \n

\n

**Intuition and Algorithm**

We use *Dijkstra\'s algorithm* to find the shortest path from our source to all targets. This is a textbook algorithm, refer to this link for more details.

Dijkstra\'s algorithm is based on repeatedly making the candidate move that has the least distance travelled.

\nIn our implementations below, we showcase both (basic) and (heap) approaches.

\n*Basic Implementation*\n

*Heap Implementation*

**Complexity Analysis**

- \n
- \n
Time Complexity: m where is the length of

\n`times`

in the basic implementation, and in the heap implementation, as potentially every edge gets added to the heap. \n - \n
Space Complexity: , the size of the graph (), plus the size of the other objects used ().

\n \n

\n

Analysis written by: @awice.

\n