Python3で再帰を使ったダイクストラ法

コード

dijkstra.py

def Dijkstra(u, w):
    Q = [i for i in range(n)]
    if len(Q) != 0:
        Q.remove(u)
        for next in G[u]:
            v = next[0]
            u_to_v = next[1]
            if distance[v] > u_to_v + w:
                distance[v] = u_to_v + w
            Dijkstra(v, u_to_v + w)


n = int(input())
G = []
for i in range(n):
    G.append([])
    b = list(map(int, input().split()))
    for j in range(0, len(b) - 1, 2):
        G[i].append([b[j], b[j + 1]])

inf = 9999
distance = [inf] * n
start = 0
distance[start] = 0
Dijkstra(start, 0)
for i in distance:
    print(i)

変数の説明

• n
  ノードの数

• G
  有向グラフ

• distance
  startと各ノードとの距離

• Q
  ノードの集合（ノードを通ったか判定用)

入出力

入力

ノードの数(n)
ノード0から進めるノードx ノード0とノードxとの距離 ・・・
ノード1から進めるノードx ノード1とノードxとの距離 ・・・
ノード2から進めるノードx ノード2とノードxとの距離 ・・・
・
・
・
ノードnから進めるノードx ノードnとノードxとの距離 ・・・

出力

startノードとノード0との最短距離
startノードとノード1との最短距離
startノードとノード2との最短距離
・
・
・
startノードとノードnとの最短距離

例

入力

8
1 5 4 9 7 8
3 15 2 12 7 4
3 3 6 11
6 9
5 4 7 5 6 20
2 1 6 13

2 7 5 6

出力

0
5
14
17
9
13
25
8