迪杰斯特拉算法

迪杰斯特拉算法

LeetCode 743. 网络延迟时间

https://blog.csdn.net/xiaoxi_hahaha/article/details/110257368

import sysdef dijkstra(graph, source):"""dijkstra算法:param graph: 邻接矩阵:param source: 出发点，源点:return:"""# 点的数量n = len(graph)# 源点到各边的初始举例，直接采用邻接矩阵对应行数据即可，注意 sys.maxsize 表示两点之间没有边dis = [sys.maxsize] * ndis[source] = 0# 初始访问过的点只有源点vis = set()# 遍历n-1趟，确定到另外n-1个点的最短路径# 每一趟都可以确定一个点到另外一个点的最短路径while True:# 找到一个距离源点最近的点node = -1for j in range(n):if j not in vis and (node == -1 or dis[j] < dis[node]):node = jif node == -1:break# 用这个最近的点来优化，源点到其他每个点的距离for j in range(n):if dis[j] > dis[node] + graph[node][j]:dis[j] = dis[node] + graph[node][j]vis.add(node)return disgraph = [[0, 5, 2, sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize],[5, 0, 1, sys.maxsize, 6, sys.maxsize, sys.maxsize],[2, sys.maxsize, 0, 6, sys.maxsize, 8, sys.maxsize],[sys.maxsize, 1, 6, 0, 1, 2, sys.maxsize],[sys.maxsize, 6, sys.maxsize, 1, 0, sys.maxsize, 7],[sys.maxsize, sys.maxsize, 8, 6, sys.maxsize, 0, 3],[sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize, 7, 3, 0],
]
print(dijkstra(graph, 0))
# assert dijkstra(graph, 0) == [0, 5, 2, 8, 9, 10, 13]

import heapqdef dijkstra(graph, source):"""使用优先队列优化的 Dijkstra 算法:param graph: 邻接矩阵:param source: 出发点，源点:return: 源点到所有其他顶点的最短路径距离"""# 点的数量n = len(graph)# 源点到各边的初始距离，直接采用邻接矩阵对应行数据即可dis = [sys.maxsize] * ndis[source] = 0  # 源点到自己的距离为0# 优先队列，存储 (距离, 节点) 对priority_queue = [(0, source)]while priority_queue:# 弹出当前距离源点最近的顶点current_distance, current_vertex = heapq.heappop(priority_queue)# 如果弹出的距离大于当前已知的最短距离，则跳过if current_distance > dis[current_vertex]:continue# 遍历当前顶点的所有邻接点for i in range(n):if dis[i] > dis[current_vertex] + graph[current_vertex][i]:dis[i] = dis[current_vertex] + graph[current_vertex][i]heapq.heappush(priority_queue, (dis[i], i))return disprint(dijkstra(graph, 0))