～ ダイクストラ法 ～ チートシート

#目次
ダイクストラ法とは
実装

もしかして：ワーシャルフロイド法

#はじめに

チートシートの扱いついてはここを読んでください

#ダイクストラ法とは

わかりやすいサイト

指定した頂点を始点とした場合に、最も到達にかかるコストが低い頂点から順に確定させていくことで、各頂点に到達するのに必要な最低コストを求めるアルゴリズム
始点となる頂点が１つに決まっている場合に有効
計算量が大きいので、始点が全頂点の場合はワーシャルフロイド法を使う
負のコストがある場合には使えないので注意

#実装

問題（Atcoderだと簡単な問題がなかったので、AIZU ONLINE JUDGEより）

Dijkstra's_algorithm.py

import heapq

N,M,S = map(int,input().split()) #頂点の数、辺の数、スタートとなる頂点の番号

root = [] #辺に関する情報を格納する配列
start = [[] for i in range(N+1)] #辺を始点ごとに分類する配列
for i in range(M):
  A,B,C = map(int,input().split()) #辺の始点、辺の終点、移動に必要なコスト
  root.append([A,B,C])
  start[A].append(i)
  
check = [] #最小コストの候補を格納する配列
heapq.heapify(check)
heapq.heappush(check, [0,S])
         
ans = [-1]*(N+1) #各頂点の最小コストを格納する配列
while True:
  cost,now = heapq.heappop(check)
  if ans[now] == -1:
    ans[now] = cost
    for i in range(len(start[now])):
      heapq.heappush(check, [cost+root[start[now][i]][2], root[start[now][i]][1]])
  if check == []:
    break

for i in range(N):
#for i in range(1,N+1): #頂点の番号が1,2,3...と振られている場合（Atcoder用）
  if ans[i] != -1:
    print(ans[i])
  else:
    print("INF")

Atcoderと異なりインデックスが0始まりなので注意（Pythonと同じだからこっちの方がありがたいけど）
高速化のために優先度付きキューを利用
ライブラリshortest_path()を使うという手もあるけど、Atcoderだとなんかめんどくさいらしい