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

問題

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

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

このグラフに対して最短経路長を求めて下さい。

出力形式として、各頂点への最短距離を頂点 $1$ から頂点 $N$ まで順番に出力して下さい。

移動できない頂点の場合は、$-1$ を出力してください

[制約]
🔹$ 2 \leqq N \leqq 100000 $
🔹$ 1 \leqq M \leqq min(100000,N(N-1))/2 $
🔹$ 1 \leqq A_i < B_i \leqq N $
🔹$ 1 \leqq C_i \leqq 10000 $

解き方・ソースコード

ダイクストラ法を使ってこの問題を解いていきます。

ソースコードの冒頭で、グラフの情報を設定しています。

ここでは、頂点数、辺の数、および各辺の情報をタプルとしてリストに格納しています。

次に、隣接リストを作成しています。

このようにしておくことで、後続の処理で各頂点からつながっている辺を効率的に参照できるようになります。

また、このコードではPythonの組み込みモジュールheapqを使って優先度付きキューを実装しています。

これにより、次に探索すべき頂点を常に距離の短い順に処理することができます。

ダイクストラ法の実装部分では、優先度付きキューから取り出した要素が確定済みの頂点(kakutei変数)である場合はスキップしています。

また、確定していない隣接頂点について、現在の距離よりも短い経路が存在する場合は、その距離を更新し、優先度付きキューに加えます。

この処理を、優先度付きキューが空になるまで繰り返します。

最後に、各頂点までの最短距離を出力しています。

頂点までの最短距離が存在しない場合は-1を出力するようにしています。

[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
53
54
55
#-------- 入力例１ ---------
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)
]
#---------------------------
import heapq

# 隣接リストの作成
# 重み付きグラフなので、各辺について (隣接頂点, 重み) のタプルを記録
G = [list() for i in range(N + 1)]
for a, b, c in edges:
    G[a].append((b, c))
    G[b].append((a, c))

# 配列・キューの初期化
# キューには (距離, 頂点番号) のタプルを記録
kakutei = [ False ] * (N + 1)
cur = [float('inf')] * (N + 1)  # 距離の暫定値
cur[1] = 0
Q = []
heapq.heappush(Q, (cur[1], 1))

# ダイクストラ法
while len(Q) > 0:
    # 次に確定させるべき頂点を求める
    # 優先度付きキュー Q の最小要素を取り除き、その要素の 2 番目の値（頂点番号）を pos に代入
    pos = heapq.heappop(Q)[1]

    # Q の最小要素が「既に確定した頂点」の場合
    if kakutei[pos] == True:
        continue

    # 暫定値 cur[x] の値を更新する
    kakutei[pos] = True
    for e in G[pos]:
        # pos = e[0], cost = e[1] で対応
        if cur[e[0]] > cur[pos] + e[1]:
            cur[e[0]] = cur[pos] + e[1]
            heapq.heappush(Q, (cur[e[0]], e[0]))

# 答えを出力
for i in range(1, N + 1):
    if cur[i] == float('inf'):
        print('頂点 {} までの最短距離 {}'.format(i, -1))
    else:
        print('頂点 {} までの最短距離 {}'.format(i, cur[i]))

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

頂点 1 までの最短距離 0

頂点 2 までの最短距離 14

頂点 3 までの最短距離 76

頂点 4 までの最短距離 22

頂点 5 までの最短距離 19

頂点 6 までの最短距離 37

各頂点への最短距離を求めることができました。