【算法基础】Dijkstra 算法

定义：

• $g[i][j]$ 表示 $v_i$ 到 $v_j $的边权重，如果没有连接，则 $g[i][j]=\infty$
• $dis[i]$ 表示 $v_k$ 到节点 $v_i$ 的最短长度，$dis[k]=0,dis[i]=\infty ,i\ne k$.

目标：

• 计算出 $dis$ 数组，也就是任何点到 $v_k$ 的距离。

step1 : 更新 $v_k$ 的所有邻居节点$v_y$的最短路径； 即：$dis[y]=g[k][y]$
step2 : 找出 这些邻居节点中路径最短的 $dis[i1]$. 此时 $dis[i1]$ 一定已经是最短的了，可以用反证法来证明。
step3 : 找出 $v_{i1}$ 的邻居节点$y^{\prime }$, 如果 $dis[i1]+g[i1][y^{\prime }]<dis[y^{\prime }]$, 则更新 $dis[y^{\prime }]=dis[i1]+g[i1][y^{\prime }]$, 否则不更新。
step4 : 找出$k,i1$之外的 $dis[i]$ 最小的值 $dis[i2]$, 重复之前的更新过程，知道取完所有点为止。

code :

leecode 743
朴素写法：

class Solution:def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:g = [[inf for _ in range(n)] for _ in range(n)]  # 邻接矩阵for x, y, d in times:g[x - 1][y - 1] = ddis = [inf] * nans = dis[k - 1] = 0  # 起始节点done = [False] * n   #是否确定为最短while True:x = -1# 找到最短的 done 是用来排除已经确定的那些点的。完成后x 记录当前最短距离的那个点。# 起始为 kfor i, ok in enumerate(done):if not ok and (x < 0 or dis[i] < dis[x]):x = i# 没有找到，也就是所有点已经全部确定后。if x < 0:return ans  # 最后一次算出的最短路就是最大的# 无法到达if dis[x] == inf:  # 有节点无法到达return -1# 因为每次都是递增的，而答案是要求最大的最短路径。ans = dis[x]  # 求出的最短路会越来越大done[x] = True  # 最短路长度已确定（无法变得更小）# 更新 x 的邻居节点的最短距离。for y, d in enumerate(g[x]):# 更新 x 的邻居的最短路dis[y] = min(dis[y], dis[x] + d)

堆优化 Dijkstra：

class Solution:def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:g = [[] for _ in range(n)]  # 邻接表for x, y, d in times:g[x - 1].append((y - 1, d))dis = [inf] * ndis[k - 1] = 0h = [(0, k - 1)]   # 二元组 (dis[i], i)while h:dx, x = heappop(h)  # 找到最短路径的 x 和其相应的 disif dx > dis[x]:  # x 之前出堆过，continue# 这里continue 是因为 对于一个x 由于更新了多次dis, 堆中科恩那个存在多个 dx, 对于那些较大的dx, 不再使用的意思。# 更新邻居for y, d in g[x]:new_dis = dx + dif new_dis < dis[y]:dis[y] = new_dis  # 更新 x 的邻居的最短路heappush(h, (new_dis, y))mx = max(dis)return mx if mx < inf else -1