Zenn
🚲

ダイクストラ法

2023/08/22に公開
Ruby
AtCoder
アルゴリズム
ダイクストラ法
優先度付きキュー
tech

特徴

ダイクストラ法は「負のコストがない」前提とすることで、アルゴリズムがシンプルになり、たんに最小コストのノードを優先的に選択するだけでよくなる。

もし負の値を持つコストが存在した場合は、そのノードにつながるノードのコストは普通に更新されるが、その新しいコストがその先のノードにも正確に伝播していくとは限らないので不整合が起きる。(その場合はベルマン-フォード法を使う)

最小コストを持つノードを毎回取得する部分は優先度付きキューに置き換えると超速くなる。

アルゴリズム

初期配置

どこも無限時間かかる。

渋谷から出発

出発点なので渋谷は0分で行ける。

渋谷→大崎

60分もかかる。

渋谷→巣鴨

1分で行ける。

ここで渋谷のターンが終わる。

巣鴨のターン

ベルマン-フォード法ではここで渋谷を除くどの街を選んでもよかったのに巣鴨を選んだ理由は4つの街の中でいちばんコストが小さかったから。最初に渋谷から始めた理由も0分で行ける渋谷のコストがいちばん小さかったから。で、巣鴨からは秋葉原までは計2分でいけることがわかる。

巣鴨から行けるのは秋葉原だけだったのでここで巣鴨のターンを終了する。

秋葉原のターン

ここで秋葉原を選んだ理由は巣鴨のときのように渋谷と巣鴨を除いたなかでいちばんコストが小さかったから。そして末広町までは計3分で行けることがわかった。

もしゴールを目的地を末広町と考えているのならここで終わる。大崎なんか60分以上が確定しているのでこれ以上計算しても無駄だからである。

末広町のターン

一応続けると「大崎 vs 末広町」は末広町の勝ちなので末広町のターンになったものの行き先がなかったので何もしない。

大崎のターン

ここまで60分もかかるせいで最後になってしまった大崎は、マイナスのコストが使えないというルールがあるせいで、これ以上の挽回は難しい。とりあえず秋葉原まで2時間で行けることがわかったが、もちろん2分で行けることが確定している秋葉原を更新することはできなかった。

すべての街を一周したのでこれで終わる。

ここまでの更新履歴

最短 渋谷 巣鴨 大崎 秋葉原 末広町
1 渋谷(0) 1 60
2 巣鴨(1) 2
3 秋葉原(2) 3
4 末広町(3)
5 大崎(60)

街を回る順番がコスト順になっているのがわかる。

実装例

graph = {
  "渋谷"   => { "巣鴨" => 1, "大崎" => 60, },
  "巣鴨"   => { "秋葉原" => 1,             },
  "秋葉原" => { "末広町" => 1,             },
  "大崎"   => { "秋葉原" => 60,            },
  "末広町" => {                            },
}

start = "渋谷"

predecessor = {}

distance = Hash.new(Float::INFINITY)
distance[start] = 0

heap = Heap.new { |e| distance[e] }
heap << start

until heap.empty?
  from = heap.pop
  graph[from].each do |to, cost|
    v = distance[from] + cost
    if v < distance[to]
      predecessor[to] = from
      distance[to] = v
      heap << to
    end
  end
end

distance         # => {"渋谷"=>0, "巣鴨"=>1, "大崎"=>60, "秋葉原"=>2, "末広町"=>3}
predecessor      # => {"巣鴨"=>"渋谷", "大崎"=>"渋谷", "秋葉原"=>"巣鴨", "末広町"=>"秋葉原"}
route_to = -> v { v && [*route_to[predecessor[v]], v] }
route_to["末広町"]  # => ["渋谷", "巣鴨", "秋葉原", "末広町"]

小手先の TLE 対策

AtCoder では実行時間が 2 秒を超えると TLE 判定になる。ダイクストラ法を使って解く問題はその TLE になりやすい。

そこで「街」を「配列インデックス」として使えるように 0 ベースの符号なし整数となるように調整する。

具体的には次のようにグラフを配列で持つようにする。

graph = [
  [[1, 1], [3, 60]],
  [[2, 1]],
  [[4, 1]],
  [[2, 60]],
]

そうすれば 0.2 秒ぐらい稼げる。

また距離のハッシュも配列にする。

distance = Array.new(graph.size, Float::INFINITY)

これで 0.1 秒ぐらい稼げる。

これらの小細工により 2 秒超えてしまう処理が 1.8 秒ぐらいに収まったりする。

その反面、

start = 0

の 0 が何の街なのかもわからない世界になってしまうので、あくまで競プロ攻略のための手段として気にとめておく。

内部データ管理方法

重要なのは、最小コストで移動できる街をどれだけ速く連続で取り出せるかである。それに合わせて変更容易性なども考慮するといろいろな書き方ができる。

訪問したら除去

準備
unvisited = graph.keys  # => ["渋谷", "巣鴨", "秋葉原", "大崎", "末広町"]
開始地点の設定
distance[start] = 0
最小値取得
from = unvisited.min_by { |e| distance[e] }  # => "渋谷"
unvisited.delete(from)                       # => "渋谷"
追加
distance[to] = new_cost
  • 良い点
    • 開始地点を設定するときに distance を更新するだけでよい
  • 悪い点
    • min_by の部分がボトルネックで競プロ問題で TLE になる

訪問したら追加

準備
visited = []
開始地点の設定
distance[start] = 0
visited << start
最小値取得
from = visited.min_by { |e| distance[e] }  # => "渋谷"
visited.delete(from)                       # => "渋谷"
追加
distance[to] = new_cost
visited << to
  • 良い点
    • 訪問したときに visited も更新しないといけないが、取り出すのが速くなる
  • 悪い点
    • min_by の部分がボトルネックで競プロ問題で TLE になる

min_by を使わない

準備
visited = []
開始地点の設定
distance[start] = 0
visited << [0, start]
最小値取得
cost, from = visited.min      # => [0, "渋谷"]
visited.delete([cost, from])  # => [0, "渋谷"]
追加
distance[to] = new_cost
visited << [new_cost, to]
  • 良い点
    • 強いて言えば min_by 相当がない言語でも動く
  • 悪い点
    • min の部分がボトルネックで競プロ問題で TLE になる

二分探索

準備
heap = []
開始地点の設定
distance[start] = 0
heap << start
最小値取得
from = heap.shift  # => "渋谷"
追加
distance[to] = new_cost
i = heap.bsearch_index { |e| distance[e] > new_cost } || heap.size  # => 0
heap.insert(i, to)                                                  # => ["巣鴨"]

優先度付きキュー

準備
heap = Heap.new
開始地点の設定
distance[start] = 0
heap << [0, start]
最小値取得
_, from = heap.pop  # => [0, "渋谷"]
追加
distance[to] = new_cost
heap << [new_cost, to]
  • 良い点
    • 取り出す処理が O(1) になる
  • 悪い点
    • 優先度付きキューに、コストを含めるのが冗長
    • 優先度付きキューを用意する必要がある

親切な優先度付きキュー

min_by のように比較条件を添えることができる優先度付きキューを使う場合。

準備
heap = Heap.new { |e| distance[e] }
開始地点の設定
distance[start] = 0
heap << start
最小値取得
from = heap.pop  # => "渋谷"
追加
distance[to] = new_cost         # 必ず先
heap << to                      # 必ず後
  • 良い点
    • 取り出す処理が O(1) になる
    • min_by を置き換えただけのようなシンプルなコードになる
  • 悪い点
    • 必ず「distance を更新してから heap に追加しなければならない」暗黙の決まりがコードからは見えにくい
    • 親切な優先度付きキューを用意する必要がある

過去問

問題 解法 考察
典型90 013 - Passing ゴールからも進める LINK
ABC340 D - Super Takahashi Bros. ダイクストラ法に気づく LINK

Discussion