はじめに
本記事ではオランダの著名な計算機械科学者Edsger Wybe Dijkstraによって1959年に提唱され、その有用性から現代でもあらゆるシーンで活用されているアルゴリズムであるDijkstra's algorithmを取り上げます。
解説の題材として扱うのはAtCorderから次の問題です。
BFSを知らない方は先にBFSの記事を読んでいただくと分かりやすいかと思います。「A64 - Shortest Path 2」は重み付き無向グラフに対する最短経路問題を解けというものです。BFSでは重みなし無向グラフの最短経路を求めることができました。ですから、今回のミッションはBFSのコードに重みの概念をどのように加えていくのかというイメージです。さっそく取り掛かっていきましょう。
モチベーション
問題を解く前にDijkstra's algorithmのモチベーションについて少し書きます。例えば地図上で最短経路を計算しようと思ったら重み付きグラフの最短経路問題を解く必要があります。経路検索から都市開発まで、今日のあらゆるインフラの根幹にこのアルゴリズムが関与しています。それほどまでに基礎的で汎用性の高い重要なアルゴリズムだと言えるのではないでしょうか。実用においては多くの場合A*やContraction Hierarchiesなどのヒューリスティックによる最適化が行われています。GoogleはContraction Hierarchiesでマップの経路検索の時間を10倍から100倍短縮しています(From A to B: Algorithms That Power Google Maps Navigation)。
ちなみに、単純にすべての道（path）をカウントする方法はどうでしょうか。これは、実はこれは現実的でありません。比較的単純なグラフでもこの方法では恐ろしい年月の計算が必要になります。具体的な数字はこのサイトでまとめてありました(フカシギの数え方)。
$10 \times 10$の正方格子の向かい合う頂点のすべてのpathを数えると、$1.568758030...\times10^{1024}$通りとなり、スーパーコンピューターで1秒間に2000億通り数えても25万年掛かってしまいます。詳しい計算時間のオーダーの予測などについては「フカシギの数え方」のページをご参照ください。
とにかくDijkstraのアルゴリズムはこれをはるかに現実的な時間、具体的には
$O((E+V)\log{V})$で実現してくれます。
では問題に移って具体的な実装を見ていきましょう。
実装
import heapq
DijkstraのアルゴリズムのBFSとの違いは優先キューを使うことです。優先キューは自動的にソートされるキューです。heapqによる優先キューはpushとpopにはそれぞれ$O(\log{N})$の計算時間を要します。
他にも優先キューを実装する方法は様々ありますが、クイックソートなどソートのアルゴリズムそのものが原理的に$O(\log{N})$の計算量を要するということが示されている以上、これより圧倒的に速い優先キューはおそらく不可能だと思います。もし詳しい方がいらっしゃればぜひご教授ください。
N, M = map(int, input().split())
node = [[] for _ in range(N)]
ここまではBFSと同じです。次にnodeの受け取りで, 変数cを使って重みを受け取ります。重みと隣接nodeの情報を一緒にまとめてtupleの形式でnodeに挿入していきます。
for _ in range(M):
a, b, c = map(int, input().split())
a -= 1
b -= 1
node[a].append((b, c))
node[b].append((a, c))
distを初期化します。infは重みの最大値と頂点数の積より大きいオーダーにしてください。
inf = 10 ** 12
dist = [inf] * N
dist[0] = 0
出発点となるnode0は当然node0との距離が0なので(0,0)をpushして開始します。
pq = []
heapq.heappush(pq, (0, 0))
このループに注目してください。BFSとの最大の違いは+1だった部分が+costに変わったことです。costは辺の重みです。
while pq:
cur_cost, cur = heapq.heappop(pq)
if cur_cost > dist[cur]:
continue
for e, cost in node[cur]:
if dist[e] > dist[cur] + cost:
dist[e] = dist[cur] + cost
heapq.heappush(pq, (dist[e], e))
ここまでくれば最後は表示です。distがinfのままの場所は最後まで通ることができなかった場所なので-1を返して終了です。
for e in dist:
if e == inf:
print(-1)
else:
print(e)
まとめ
ここまでのコードをまとめると次のようになります。
import heapq
N, M = map(int, input().split())
node = [[] for _ in range(N)]
for _ in range(M):
a, b, c = map(int, input().split())
a -= 1
b -= 1
node[a].append((b, c))
node[b].append((a, c))
inf = 10 ** 12
dist = [inf] * N
dist[0] = 0
pq = []
heapq.heappush(pq, (0, 0))
while pq:
cur_cost, cur = heapq.heappop(pq)
if cur_cost > dist[cur]:
continue
for e, cost in node[cur]:
if dist[e] > dist[cur] + cost:
dist[e] = dist[cur] + cost
heapq.heappush(pq, (dist[e], e))
for e in dist:
if e == inf:
print(-1)
else:
print(e)
どうでしょうか。少し寄り道をして最短経路から外れた冗長な説明になってしまいましたが今日はこのあたりで。