说明

从某个点出发，求最短路径算法，带路径输出

模版

可以使用最小堆优化

# 变量
g = [[INF]*n for i in range(n)] #图的初始化
dis = [INF]*n #距离
vis = [False]*n #是否已经求的最短路径
pre = [0] * n #前一个节点信息
# 初始化
n, m=map(int, input().split()) #n个节点 m条边
while m: #读取m条边
    a,b,c=map(int, input().split())
    g[a][b]=c
    g[b][a]=c
    m -= 1
dijkstra(n)

def dijkstra(n):
    #从节点1出发，初始化距离
    for i in range(1, n+1): 
        dis[i]=g[1][i]

    dis[1]=0 #节点1加入K
    vis[1]=True #打上标记
     next=1 #下一个即将加入的，1只是用来初始化
    for i in range(2, n+1):# 1已经加入K，从2开始
        mini=INF
        for j in range(1, n+1):# 寻找最短距离的next
            if vis[j]==False and dis[j]<mini:
                mini=dis[j]
                next=j

        vis[next]=True #打上集合K的标记
        for j in range(1, n+1): #是否可以经过next更新其他节点的距离
            if vis[j]==False and dis[next]+g[next][j]<dis[j]:
                dis[j]=dis[next]+g[next][j]
                pre[j]=next