ダイクストラ法

今回はダイクストラ法をやっていきます。
まず、ダイクストラ法の説明については下記動画がとてもわかりやすいです。
https://youtu.be/X1AsMlJdiok

ちなみにダイクストラ法では負の辺があるとき使えません。
負の辺があるときはベルマン・フォード法を使いましょう。
負の辺があるときにダイクストラ法を使うと負の閉路がある場合があるので、ループし続けてしまうため、処理が終わりません。

入力は以下が与えられるとします

4 5 頂点の数、辺の数
0 1 2 頂点、隣接する頂点、辺の重み
0 2 4
1 2 1
1 3 3
2 3 1

図で表わすと以下のようになります

ではコードを書いていきます

from heapq import heappush, heappop,heapify

INF=10**9
V,E=map(int,input().split())
Graph=[[] for _ in range(V)]
dist=[INF]*(V)#とりあえず大きな数値を入れておく
dist[0]=0#頂点0から始めるので頂点0にいくコストは0
priority_queue=[[0,0]] #現在のdist,今いる頂点
heapify(priority_queue)#優先度付きキューに変換


for i in range(E):
    s,t,d=map(int,input().split())
    Graph[s].append([t,d])

今回はheapqというライブラリを使っています。
使い方は下記記事を参考にしました。
https://qiita.com/ell/items/fe52a9eb9499b7060ed6

処理の部分を書いていきます

while priority_queue:
    print(priority_queue)
    v=heappop(priority_queue)[1]#先頭の要素を取り出し、削除
    
    for j,k in Graph[v]:#頂点vと隣接する頂点を訪れる
        if dist[v]+k<dist[j]:#隣接する頂点jの最もコストが低い所に行く
            dist[j]=dist[v]+k#頂点jに行くコスト
            heappush(priority_queue,[dist[j],j])#最短距離を更新したら、その頂点へのコスト、頂点をキューに追加

BFSと似たようなコードになっています。
キューがなくなるまで繰り返します。
if文は例えば頂点2に行くルートが今回の場合頂点0-1-2と頂点0-2の2パターンがあります。
頂点0-2のパターンは頂点2に行くコストは4となります。
頂点0-1-2のパターンは3となり、上記のパターンよりコストが小さくなるので3に上書きします。
優先度付きキューなのでキューに要素を挿入したら、ヒープ内の他の要素はそれにあわせて調整されるようになっているそうです。
コード全体

from heapq import heappush, heappop,heapify

INF=10**9
V,E=map(int,input().split())
Graph=[[] for _ in range(V)]
dist=[INF]*(V)#とりあえず大きな数値を入れておく
dist[0]=0#頂点0から始めるので頂点0にいくコストは0
priority_queue=[[0,0]] #現在のdist,今いる頂点
heapify(priority_queue)#優先度付きキューに変換

for i in range(E):
    s,t,d=map(int,input().split())
    Graph[s].append([t,d])
    
while priority_queue:
    v=heappop(priority_queue)[1]#先頭の要素を取り出し、削除
    
    for j,k in Graph[v]:#頂点vと隣接する頂点を訪れる
        if dist[v]+k<dist[j]:#隣接する頂点jに最もコストが低い所を通って行く
            dist[j]=dist[v]+k#頂点jに行くコスト
            heappush(priority_queue,[dist[j],j])#最短距離を更新したら、その頂点へのコスト、頂点をキューに追加
            
print(dist)

参考記事
https://qiita.com/ageprocpp/items/cdf67e828e1b09316f6e#%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95
https://mirucacule.hatenablog.com/entry/2020/05/21/124026