迪杰斯特拉算法是由荷兰计算机科学家在1956年发现的算法，此算法使用类似广度优先搜索的方法解决了带权图的单源最短路径问题。它是一个贪心算法。
核心思想：
更新邻接节点的最短距离
优点：
- 解决单个来源的最短路径
- 能解决非负权的带权图
缺点： - 不能处理带有负权边的图(可能得不到最优解，认为是无法处理负权图)，只能处理非负权图。
- 多源无法解决
例题：
力扣743
有 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
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
g = [[float('inf')] * n for _ in range(n)] # 初始化一个邻接矩阵
for x, y, time in times: # 把权加入矩阵
g[x - 1][y - 1] = time
dist = [float('inf')] * n # 初始化源点到所有点的距离为正无穷
dist[k - 1] = 0 # 源点到自身的距离为0
used = [False] * n # 被使用的点的矩阵
for _ in range(n):
x = -1 # x = -1 是为了初始化, 这个初始实际上可以为任何值
# 循环执行完找到当前最小的dist
for y, u in enumerate(used):
if not u and (x == -1 or dist[y] < dist[x]):
x = y
used[x] = True
for y, time in enumerate(g[x]): # 更新当前阶段 源点到 y的最小距离
dist[y] = min(dist[x]+time, dist[y])
ans = max(dist)
return ans if ans < float('inf') else -1
