Dijkstra算法有这一篇就够啦

Inf = 999999
#Dijkstra算法是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题
#核心思想是:每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。
def Dijkstra(start, end):
    #未访问过的顶点集合
    queue={i:Inf for i in range(start+1,n+1)}
    #显而易见,起点到起点到距离为0
    dist[start] = 0
    while start is not end :
        #存储当前结点的所有邻接节点,例如,1的邻接节点是2和8
        pos = [i for i in range(1,n+1) if map[start][i] < Inf]
        #更新邻接节点到始点距离
        for i in pos:
            #更新这些路径到达起点的位置,可能之前有路径到达过此结点
            dist[i] = min(dist[i], dist[start] + map[start][i])
            #更新剩余结点到起点到距离
            if i in queue: queue[i]= dist[i]
        #在未访问过的顶点集合中选择一条距离起点最近到顶点,前行
        start = min(queue,key = queue.get)
        #用弹出队列到方式标记 最短路径
        queue.pop(start)
        #我们此时来到了下一个顶点,后面就是重复之前到过程,我们加快速度
    return -1 if dist[end] is Inf else dist[end]
if __name__ == "__main__":
    n, m = [int(i) for i in input().split(" ")]
    # 初始化个点到起点到距离
    map = [[Inf for _ in range(n + 1)] for _ in range(n + 1)]
    dist = [Inf for _ in range(n + 1)]
    for _ in range(m):
        u, v, d = [int(x) for x in input().split(" ")]
        map[u][v] = map[v][u] = d
    print(Dijkstra(1, 5))
评论注意事项

回复(0)