初めてのダイクストラ法

ダイクストラ法

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

いっぱいコメントアウトがあります。（お見苦しいです。）

無限大を999999にしています。
リストvが地点までのコストの合計（最後には一番ちいさくなる）
リストvkが最小のコストが確定したらTrueにするものです。

データ

地点の数、道の数
地点→地点　コスト
7 12
0 1 16
0 2 8
0 3 15
1 6 78
1 5 13
2 1 13
2 4 10
2 5 17
2 3 21
3 5 33
4 6 15
5 6 52

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])

上記が初めてのダイクストラ法の実装でした。

次は後半のワーシャル–フロイド法も実装してみたいと思います。

上と同じ経路を双方向にしてワーシャル–フロイド法にしてみました。
こんなに短いプログラムでどうしてちゃんとできるのか不思議です。

Floyd–Warshall.py

# coding: utf-8
# Your code here!
#ワーシャルフロイド法
n,m=[int(i) for i in input().split()]
#print(n,m)
a=[[999999]*n for i in range(n)]
for i in range(m):
   a1=[int(j) for j in input().split()]
   #print(a1)
   a[a1[0]][a1[1]]=a1[2]
   a[a1[1]][a1[0]]=a1[2]
   #print(a1[0])
for i in range(n):
    a[i][i]=0
for i in a:
    print(i)
print()
for k in range(n):
    for i in range(n):
        for j in range(n):
            a[i][j]=min(a[i][j],a[i][k]+a[k][j])
for i in a:
    print(i)