:orphan:

Network Delay Time
==================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/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] = (u``\ :sub:```i```\ ``, v``\ :sub:```i```\ ``, w``\ :sub:```i```\ ``)``,
where ``u``\ :sub:```i``` is the source node, ``v``\ :sub:```i``` is the
target node, and ``w``\ :sub:```i``` 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:**

|image1|

::


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

**Example 2:**

::


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

**Example 3:**

::


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

 

**Constraints:**

- ``1 <= k <= n <= 100``
- ``1 <= times.length <= 6000``
- ``times[i].length == 3``
- ``1 <= u``\ :sub:```i```\ ``, v``\ :sub:```i```\ ``<= n``
- ``u``\ :sub:```i```\ ``!= v``\ :sub:```i```
- ``0 <= w``\ :sub:```i```\ ``<= 100``
- All the pairs ``(u``\ :sub:```i```\ ``, v``\ :sub:```i```\ ``)`` are
  **unique**. (i.e., no multiple edges.)

.. |image1| image:: https://assets.leetcode.com/uploads/2019/05/23/931_example_1.png

.. highlight:: python

Pattern
-------
Depth-First Search, Breadth-First Search, Graph Theory, Heap (Priority Queue), Shortest Path

Approaches
----------

.. tab-set::

    .. tab-item:: Dijkstra

        **Code**

        .. literalinclude:: ../problems/medium/network-delay-time/network_delay_time__dijkstra.py
            :language: python
            :lines: 11-

        **Test**

        >>> from network_delay_time__dijkstra import networkDelayTime
        >>> networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)
        2
        >>> networkDelayTime([[1,2,1]], 2, 1)
        1
        >>> networkDelayTime([[1,2,1]], 2, 2)
        -1

        .. autofunction:: network_delay_time__dijkstra.networkDelayTime