迪杰斯特拉算法

LeetCode 743. 网络延迟时间

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

import sys


def dijkstra(graph, source):
    """
    dijkstra算法
    :param graph: 邻接矩阵
    :param source: 出发点，源点
    :return:
    """
    # 点的数量
    n = len(graph)
    # 源点到各边的初始举例，直接采用邻接矩阵对应行数据即可，注意 sys.maxsize 表示两点之间没有边
    dis = [sys.maxsize] * n
    dis[source] = 0
    # 初始访问过的点只有源点
    vis = set()
    # 遍历n-1趟，确定到另外n-1个点的最短路径
    # 每一趟都可以确定一个点到另外一个点的最短路径
    while True:
        # 找到一个距离源点最近的点
        node = -1
        for j in range(n):
            if j not in vis and (node == -1 or dis[j] < dis[node]):
                node = j
        if 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 dis


graph = [
    [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 heapq


def dijkstra(graph, source):
    """
    使用优先队列优化的 Dijkstra 算法
    :param graph: 邻接矩阵
    :param source: 出发点，源点
    :return: 源点到所有其他顶点的最短路径距离
    """
    # 点的数量
    n = len(graph)
    # 源点到各边的初始距离，直接采用邻接矩阵对应行数据即可
    dis = [sys.maxsize] * n
    dis[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 dis


print(dijkstra(graph, 0))