初めてのダイクストラ法

はじめてダイクストラ法を学習してプログラムしてみたので覚書として書いています。

早川桃子先生のYouTube
離散数学入門#5: 最短経路問題：ダイクストラ法とワーシャル–フロイド法
https://m.youtube.com/watch?v=e6X2gDTZYCQ
の例題の実装を試みてみました。
実行環境はpaiza.ioです。

dijkstra.py

n,m=[int(i) for i in input().split()]
#print(n,m)
a=[]
for i in range(m):
   a.append([int(j) for j in input().split()])
#print(a)
v=[999999]*n
vk=[False]*n
#print(v,vk)
v[0]=0
#print(v,vk)
#j=0
while True:
    v1=999999
    i1=999999
    for i in range(n):
        if v[i]<v1 and vk[i]==False:
            i1=i
            v1=v[i]
    if i1==999999:
        break
    #print(i1,v1)
    vk[i1]=True
    for a1 in a:
        #print(a1)
        if a1[0]==i1:
            v[a1[1]]=min(v[a1[1]],v[i1]+a1[2])
            #print(v,vk)
    #j+=1
print("ans",v,vk)
#print(a)
#後戻り
#print(v[6])
i1=6
rp=[]
rp.append(i1)
#j=0
while True:
    if i1==0:
        break
    for a1 in a:
        if a1[1]==i1:
            #print(a1,v[i1],v[a1[0]])
            if v[i1]-a1[2]==v[a1[0]]:
                #print(a1,v[i1],v[a1[0]]," ",end="")
                i1=a1[0]
                #print(i1)
                rp.append(i1)
                #print(rp)
                #j+=1
                break
print("pass",rp[::-1])