GRL1A 単一始点最短経路

この記事で使うアルゴリズム

ダイクストラ法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

この問題はダイクストラ法を用いて解くことができます。

ポイント

ダイクストラ法の計算量は下記のようになります。

- リスト: O(|V|^2)
- 優先度付きキュー（二分ヒープ）: O((|V|+|E|)log|V|)
- 優先度付きキュー（フィボナッチヒープ）: O(|E|+|V|log|V|)

いつも優先度付きキューを使えば良いというわけではありません。完全グラフの場合は|V|^2と|E|のオーダーが等しくなるため、リストが最も高速になります。

しかし、この問題の場合は優先度付きキューを用いるのが良いでしょう。Pythonで優先度付きキュー（二分ヒープ）を実装する際は、標準ライブラリのheapqを利用すると良いです。

コード

import heapq
INF = 10**10

V, E, r = map(int,input().split())
adj = [[] for i in range(V)] # 隣接リスト

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

dists  = [INF for i in range(V)] # 重みの和
dists[r] = 0
pq = [(0, r)] # 二分ヒープの実体はリストやタプルとして表現する
　            # (重みの和, ノード番号)
while(pq):
    d, node = heapq.heappop(pq)
    if (d > dists[node]): # 探索の対象にする必要があるか確認
        continue
    for next, cost in adj[node]:
        if d + cost < dists[next]:# 探索の対象にする必要があるか確認
            dists[next] = d + cost # 次のノードにおける重みの和
            heapq.heappush(pq, (dists[next],next))
for d in dists:
    if d == INF:
        print ('INF')
    else:
        print (d)

記事情報

• 投稿日：2020年4月25日
• 最終更新日：2020年5月10日