AOJ - ALDS1_12_B (ダイクストラ法) を解いてみた

AOJ - ALDS1_12は、重み付きのグラフアルゴリズムです。

最短経路 ダイクストラ法 | アルゴリズムとデータ構造 | Aizu Online Judge

この問題が解けるとAtCoderの以下の問題も解けます

abc012.contest.atcoder.jp

問題設定

最短経路問題というのは、２つのノード間を結ぶ経路の中で重みが最小の経路を求める最適化問題のことらしい。

詳しいところはWikipediaをよめばよろし　→　最短経路問題 - Wikipedia

一筆書きは求められていません。一度訪問したノードからは再出発できます。

最短経路問題の分類とアルゴリズムの使いどころ

今回はWikipediaの記述が役に立っています。最短経路問題は条件ごとに複数のアルゴリズムが適用されるみたいです。

Wikipediaの記述を整理すると…

[最短経路問題]
   │
   ├── [ 2頂点対最短経路問題 ] (単一始点と同じロジックで対応できる)
   │ 
   ├── [ 単一始点最短経路問題（SSSP） ]　　　　　　　　　　
   │             ├── [ 辺の重みなし有向グラフ ]　　　　　　→　幅優先探索
   │             ├── [ 辺の重みが非負値の有向グラフ ]　　　→　ダイクストラ法
   │             └── [ 辺の重みが任意の実数の有向グラフ ]　→　ベルマン-フォード法
   │
   └── [ 全点対最短経路問題 ]
   　             └── ワーシャル-フロイド法

チラチラ数学の論文っぽい参照が散見されますが、競プロのために論文は読まんでいいはず…。とにもかくにも、最短経路を求めるときに辺の重みがマイナスじゃなけりゃダイクストラ法を使えばいいのです。あと、もう一つダイクストラ法には制約があって、有向グラフ（辺が一方通行）のものしか適用できないようです。

AOJの問題の注意

• プリム法は無向グラフが対象でしたが、ダイクストラ法のグラフは有向グラフです
• プリム法は1-indexedなグラフでしたが、なぜかダイクストラ法のほうは0-indexedです*1

グラフをGraphvizでビジュアル化する

文章だとわからんので、グラフをGraphvizでビジュアル化してみました。

AOJ ALDS1_12_Bのグラフを図示

0から出発したときに、各ノードに到達する時間（重み）を求めます。正解は以下

• 左がノード、右がそのノードまでの０からの距離

0 0
1 2
2 2
3 1
4 3

ノードは５個ですが、すでに目検では最短経路の探索は難しくなっています。

Wikipediaの記述にあるようにこのアルゴリズムはカーナビなどの地図上の２点の最短経路を求めるために使われていたりするのでした。

アルゴリズム

疑似コード

ダイクストラ法 - Wikipedia

Wikipediaの疑似コードを見ると、ソースの内容が前回のプリム法と似ていることに気付くかもしれません。プリム法ではノードの距離の比較の際、隣接行列の値と現在の距離だけを比較していましたが、ダイクストラ法は隣接行列の値と現在もっているノードの距離と現在の距離を比較します。

再びヨークカレッジ ペンシルバニア校/York College of Pennsylvaniaのレジェメを見る。

Lecture 22: Single Source Shortest Paths - Dijkstra's Algorithm

DIJKSTRA(G,w,s)
   INITIALIZE-SINGLE-SOURCE(G,s)
   S = ∅
   Q = G.V
   while Q ≠ ∅
      u = EXTRACT-MIN(Q)
      S = S ∪ {u}
      for each vertex v ∈ G.Adj[u]
         RELAX(u,v,w) 
         # ↑ ここの関数は単に分割されとるだけ
         # 一番下のRELAX関数をここにコピペするとプリム法とほぼ同じ

INITIALIZE-SINGLE-SOURCE(G,s)
   for each vertex v ∈ G.V
      v.d = ∞
      v.pi = NIL
   s.d = 0

RELAX(u,v,w)
   if v.d > u.d + w(u,v)
      v.d = u.d + w(u,v)
      v.pi = u

自分の解答

Solution for ALDS1_12_B: Single Source Shortest Path I by hiroyuking

*1:統一してくれ…