当前位置：首页 > news >正文

【算法基础】Dijkstra 算法

news 来源：原创 2024/9/20 7:58:00

定义：

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

目标：

计算出 $d i s$ 数组，也就是任何点到 $v_k$ 的距离。

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

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