ダイクストラ法②（最短経路）

問題

次のような重み付き無向グラフが与えられます。

🔹頂点数は $N$、辺の数は $M$ です。
🔹$i$ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結び、長さは $ C_i $ です。

頂点 $1$ から頂点 $N$ までの具体的な最短経路を１つ出力して下さい。

解き方・ソースコード

前回記事では、グラフにおける最短経路長を求めましたが、今回は最短経路（道筋）を求めます。

まず、与えられた辺の情報を使ってグラフを表現するために、隣接リスト g を作成します。このリストは、各頂点につながる辺の情報を保持するために使用されます。

次に、最短経路を求めるための初期化を行います。

ここでは、距離を表す cost リストと、最短経路の復元に使用する back リストを作成し、それぞれ無限大と -1 で初期化します。

また、探索を行うためのキュー q を作成し、スタート地点となる頂点の情報をキューに追加します。

その後、以下の処理をキューが空になるまで繰り返します。

1. キューから距離が最小の頂点を取り出す。
2. 取り出した頂点に隣接する頂点について、距離を更新する必要がある場合は、push 関数を呼び出して距離を更新し、キューに頂点の情報を追加する。

この push 関数は、最短経路探索中に頂点に訪れる部分を関数化したものです。

この関数では、新たな頂点に到達した場合に距離を更新し、その頂点を探索するためにキューに情報を追加します。

最短経路探索が終了したら、back リストを使って、スタート地点から終点までの最短経路を復元します。

最後に、求めた最短経路を順番に出力します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#-------- 入力例１ ---------
N = 6       # 頂点数
M = 7       # 辺の数
# つながっている頂点とその距離
edges = [
    (1, 2, 14),
    (1, 4, 22),
    (2, 3, 62),
    (2, 5, 5),
    (3, 6, 52),
    (4, 5, 38),
    (5, 6, 18)
]
#---------------------------
from heapq import heappush, heappop

g = [[] for _ in range(N)]
for A, B, C in edges:
    A -= 1
    B -= 1
    g[A].append((B, C))
    g[B].append((A, C))

INF = 1 << 61
cost = [INF] * N
back = [-1] * N
q = []

# 頂点に訪れる部分を関数化
def push(prev, i, c):
    if cost[i] <= c:
        return
    cost[i] = c
    back[i] = prev
    heappush(q, (c, i))

# 復元の都合上後ろから ダイクストラ法を行う
push(-1, N - 1, 0)
while q:
    c, x = heappop(q)
    if cost[x] != c:
        continue # 同じ頂点から複数回探索しない
    for j, d in g[x]:
        push(x, j, c + d)

# 最短経路を復元
ans = [0]
while ans[-1] != N - 1:
    ans.append(back[ans[-1]])

for x in ans:
    print(x + 1)

[実行結果（入力例１）]

1

2

5

6

最短経路（道筋）は【頂点１➡頂点２➡頂点５➡頂点６】であることが確認できました。