-[1584. Min Cost to Connect All Points](en/1001-2000/1584-min-cost-to-connect-all-points.md) was solved in_Python, Java, C++, JavaScript, C#, Go, Ruby_ and 2 ways.

-[207. Course Schedule](en/1-1000/207-course-schedule.md) was solved in_Python, Java, C++, C#_ and 2 ways.

-[1514. Path with Maximum Probability](en/1001-2000/1514-path-with-maximum-probability.md) was solved in_Python_ and 2 ways.

-[743. Network Delay Time](en/1-1000/743-network-delay-time.md) was solved in_Python_ and 2 ways.

More LeetCode problems will be added soon...

More LeetCode problems will be added soon.

</details>

We can solve it via both**Bellman-Ford algorithm** and**Dijkstra's algorithm**.

`Bellman-Ford algorithm` has less code and can handle the situation of**negative** edge weights, but it is slower than`Dijkstra's algorithm`.

`Dijkstra's algorithm` always takes the shortest path, so it is more efficient, but it requires writing more code and it cannot handle the situation of**negative** edge weights.

For a detailed description of**Dijkstra's algorithm**, please refer to[1514. Path with Maximum Probability](../1001-2000/1514-path-with-maximum-probability.md).

* Time:`O()`.

* Space:`O()`.

**V**: vertex count,**E**: Edge count.

* Time:`O(V * E)`.

* Space:`O(V)`.

* Time:`O(E * log(E))`.

* Space:`O(V + E)`.

classSolution:

defnetworkDelayTime(self,items: List[List[int]],n:int,start:int) ->int:

min_distances= [float('inf')]* (n+1)

min_distances[start]=0

defnetworkDelayTime(self,edges: List[List[int]],n:int,start:int) ->int:

min_times= [float('inf')]* (n+1)

min_times[start]=0

for _inrange(n-1):

for source_node, target_node, timein edges:# process edges directly

if min_times[source_node]==float('inf'):

target_time= time+ min_times[source_node]

if target_time< min_times[target_node]:

min_times[target_node]= target_time

result=max(min_times[1:])

if result==float('inf'):

return result

classSolution:

defnetworkDelayTime(self,edges: List[List[int]],n:int,start:int) ->int:

min_times= [float('inf')]* (n+1)

min_times[start]=0

node_to_pairs= defaultdict(set)

for source, target,distanceinitems:

node_to_pairs[source].add((target,distance))

for source, target,timeinedges:# process nodes first, then their edges

node_to_pairs[source].add((target,time))

for _inrange(n-1):

for node, min_distanceinenumerate(min_distances):

if min_distance==float('inf'):

for node, min_timeinenumerate(min_times):# process nodes first

if min_time==float('inf'):

for target_node, timein node_to_pairs[node]:# process edges of the node

target_time= time+ min_time

if target_time< min_times[target_node]:

min_times[target_node]= target_time

result=max(min_times[1:])

if result==float('inf'):

return result

import heapq

classSolution:

defnetworkDelayTime(self,edges: List[List[int]],n:int,start_node:int) ->int:

min_times= [float('inf')]* (n+1)

min_times[start_node]=0

node_to_pairs= defaultdict(set)

for source, target, timein edges:

node_to_pairs[source].add((target, time))

priority_queue= [(0, start_node)]

while priority_queue:

current_time, current_node= heapq.heappop(priority_queue)

for target_node, timein node_to_pairs[current_node]:

target_time= time+ current_time

if target_time< min_times[target_node]:

min_times[target_node]= target_time

heapq.heappush(priority_queue, (target_time, target_node))

result=max(min_times[1:])

if result==float('inf'):

return result

import heapq

classSolution:

defnetworkDelayTime(self,edges: List[List[int]],n:int,start_node:int) ->int:

min_times= [float('inf')]* (n+1)

min_times[start_node]=0

node_to_pairs= defaultdict(set)

visited= [False]* (n+1)# added 1

for source, target, timein edges:

node_to_pairs[source].add((target, time))

priority_queue= [(0, start_node)]

while priority_queue:

current_time, current_node= heapq.heappop(priority_queue)

if visited[current_node]:# added 3

visited[current_node]=True# added 2

for target_node, timein node_to_pairs[current_node]:

if visited[target_node]:# added 4

for target_node, distancein node_to_pairs[node]:

distance_= distance+ min_distance

target_time= time+ current_time

if distance_< min_distances[target_node]:

min_distances[target_node]= distance_

if target_time< min_times[target_node]:

min_times[target_node]= target_time

heapq.heappush(priority_queue, (target_time, target_node))

result=max(min_distances[1:])

result=max(min_times[1:])

if result==float('inf'):

力扣链接：[743. 网络延迟时间](https://leetcode.cn/problems/network-delay-time), 难度:**中等**。

有`n` 个网络节点，标记为`1` 到`n`。

给你一个列表`times`，表示信号经过**有向** 边的传递时间。`times[i] = (ui, vi, wi)`，其中`ui` 是源节点，`vi` 是目标节点，`wi` 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回`-1` 。

**输入**:`times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2`

**输出**:`2`

**输入**:`times = [[1,2,1]], n = 2, k = 1`

**输出**:`1`

**输入**:`times = [[1,2,1]], n = 2, k = 2`

**输出**:`-1`

- 所有`(ui, vi)` 对都**互不相同**（即，不含重复边）

<details>

<summary>提示 1</summary>

We visit each node at some time, and if that time is better than the fastest time we've reached this node, we travel along outgoing edges in sorted order. Alternatively, we could use Dijkstra's algorithm.

</details>

本题可用**Bellman-Ford算法** 或**Dijkstra算法** 解决。

`Bellman-Ford`算法代码量少，还能处理`边`权值为**负数**的情况，但较慢。

`Dijkstra算法`因为始终走最短路径，所以执行**效率高**！但代码量大，无法处理`边`权值为**负数**的情况。

**Dijkstra算法**的详细说明，请参考[1514. 概率最大的路径](../1001-2000/1514-path-with-maximum-probability.md)。

**V**: 顶点数量，**E**: 边的数量。

* 时间:`O(V * E)`.

* 空间:`O(V)`.

* 时间:`O(E * log(E))`.

* 空间:`O(V + E)`.

classSolution:

defnetworkDelayTime(self,edges: List[List[int]],n:int,start:int) ->int:

min_times= [float('inf')]* (n+1)

min_times[start]=0

for _inrange(n-1):

for source_node, target_node, timein edges:# process edges directly

if min_times[source_node]==float('inf'):

target_time= time+ min_times[source_node]

if target_time< min_times[target_node]:

min_times[target_node]= target_time

result=max(min_times[1:])

if result==float('inf'):

return result

classSolution:

defnetworkDelayTime(self,edges: List[List[int]],n:int,start:int) ->int:

min_times= [float('inf')]* (n+1)

min_times[start]=0

node_to_pairs= defaultdict(set)

for source, target, timein edges:# process nodes first, then their edges

node_to_pairs[source].add((target, time))

for _inrange(n-1):

for node, min_timeinenumerate(min_times):# process nodes first

if min_time==float('inf'):

for target_node, timein node_to_pairs[node]:# process edges of the node

target_time= time+ min_time

if target_time< min_times[target_node]:

min_times[target_node]= target_time

result=max(min_times[1:])

if result==float('inf'):

return result

import heapq

classSolution:

defnetworkDelayTime(self,edges: List[List[int]],n:int,start_node:int) ->int:

min_times= [float('inf')]* (n+1)

min_times[start_node]=0

node_to_pairs= defaultdict(set)

for source, target, timein edges:

node_to_pairs[source].add((target, time))

priority_queue= [(0, start_node)]

while priority_queue:

current_time, current_node= heapq.heappop(priority_queue)

for target_node, timein node_to_pairs[current_node]:

target_time= time+ current_time

if target_time< min_times[target_node]:

min_times[target_node]= target_time

heapq.heappush(priority_queue, (target_time, target_node))

result=max(min_times[1:])

if result==float('inf'):

return result

import heapq

classSolution:

defnetworkDelayTime(self,edges: List[List[int]],n:int,start_node:int) ->int:

min_times= [float('inf')]* (n+1)

min_times[start_node]=0

node_to_pairs= defaultdict(set)

visited= [False]* (n+1)# added 1

for source, target, timein edges:

node_to_pairs[source].add((target, time))

priority_queue= [(0, start_node)]

while priority_queue:

current_time, current_node= heapq.heappop(priority_queue)

if visited[current_node]:# added 3

visited[current_node]=True# added 2

for target_node, timein node_to_pairs[current_node]:

if visited[target_node]:# added 4

target_time= time+ current_time

if target_time< min_times[target_node]:

min_times[target_node]= target_time

heapq.heappush(priority_queue, (target_time, target_node))

result=max(min_times[1:])

if result==float('inf'):

return result