|本文
1092
字|
需要时间:
4
分钟|
一、Dijkstra 迪杰斯特拉
- 用于计算一个节点到其他节点的最短路径
- 贪心算法
- 「前提：图中不能有负权边」
二、基本思想
- 通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。
- 此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
- 初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 … 重复该操作，直到遍历完所有顶点。
三、图解算法
四、leetcode相关题目
- 首先，Dijkstra 算法需要存储各个边权，由于本题节点数量不超过 100100，所以代码中使用了邻接矩阵 g[i][j] 存储从点 i 到点 j 的距离。若两点之间没有给出有向边，则初始化为 inf。算法还需要记录所有点到源点的最短距离，代码中使用了 dist[i] 数组存储源点到点 i 的最短距离，初始值也全部设为 inf。由于本题源点为 KK，所以该点距离设为 0。
- 其次，Dijkstra 算法需要标记某一节点是否已确定了最短路，在代码中使用了 used[i] 数组存储，若已确定最短距离，则值为 true，否则值为 false。
- 之所以 inf 设置为 INT_MAX / 2，是因为在更新最短距离的时候，要有两个距离相加，为了防止溢出 int 型，所以除以 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
# 标记数组
used = [False] * n
for _ in range(n):
# 找到未标记最近的点
x = -1
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]):
dist[y] = min(dist[y], dist[x] + time)
ans = max(dist)
return ans if ans < float('inf') else -1
