【算法基础】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] = d

        dis = [inf] * n
        ans = dis[k - 1] = 0  # 起始节点
        done = [False] * n   #是否确定为最短
        while True:
            x = -1
            # 找到最短的 done 是用来排除已经确定的那些点的。完成后x 记录当前最短距离的那个点。
            # 起始为 k
            for 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] * n
        dis[k - 1] = 0
        h = [(0, k - 1)]   # 二元组 (dis[i], i)
        while h:
            dx, x = heappop(h)  # 找到最短路径的 x 和其相应的 dis
            if dx > dis[x]:  # x 之前出堆过，
                continue
			# 这里continue 是因为 对于一个x 由于更新了多次dis, 堆中科恩那个存在多个 dx, 对于那些较大的dx, 不再使用的意思。
            # 更新邻居
            for y, d in g[x]:
                new_dis = dx + d
                if new_dis < dis[y]:
                    dis[y] = new_dis  # 更新 x 的邻居的最短路
                    heappush(h, (new_dis, y))
        mx = max(dis)
        return mx if mx < inf else -1