Zenn
🚲

ベルマン-フォード法

2023/08/18に公開
Ruby
アルゴリズム
#
最短経路問題
#
ベルマンフォード法
tech

基本

どの街に行くにしても無限の時間(∞)がかかる

渋谷から出発する

もうそこにいるので渋谷までの所要時間は0分とする。

次に渋谷から秋葉原

説明の都合上1分で行ける。

続いて渋谷から大崎

こっちは60分もかかるので大崎経由はやめたほうがよさそうだ。

次に秋葉原を基点に調べる

末広町までは1分(徒歩)で行ける。ということは秋葉原まで1分かかっているので末広町までは計2分になる。このあたりは図を見れば一瞬でわかる。

ところで渋谷のあとに大崎ではなく秋葉原を選んだのはなぜか。それは内部の街の並びがそうだったからであって特別な意図はない。なんなら出発地点の渋谷から始める必要もない。どこから始めてもいいのでとりあえずそれぞれの街を順番に回って矢印の隣町までの時間を調べていく。

同様に大崎を基点に調べる

渋谷・秋葉原の次は大崎を基点に調べる。ただ大崎に来るにはすでに60分もかかっているのでここから行ける経路を調べるのは無駄に思える。が、秋葉原まではマイナス60分。どういうわけかライフイズストレンジのマックスのごとく時間だけを巻き戻すことで0分で行けることがわかった。それは渋谷から山手線外回りで秋葉原に行く時間よりも速いので秋葉原までの到達時間を1分から0分に更新しておく。

最後に末広町を基点に調べる

どこにも行き先がないので何もやることがなかった。

とりあえずこれで渋谷・秋葉原・大崎・末広町を順に一周した。

ダイクストラ法では一周したりゴールに辿りついた時点で終わってもよかったのだがベルマン-フォード法は何度も繰り返す。

二周目

  1. 渋谷から秋葉原と大崎は変更なし
  2. 秋葉原から末広町は変更あり
    秋葉原まで1分で来れていたのが0分になったことで末広町まで1分で行けることがわかった
  3. 大崎から秋葉原は変更なし
  4. 末広町は行き先がないのでやることなし

三周目も繰り返す

三周目は何も更新がなかった。最終的には最大「街の数 - 1」回繰り返せば収束するのだけど今回のように更新がなければ早めに収束したということで終わる。

これまでの更新履歴

渋谷 秋葉原 大崎 末広町
0
1 0 60 2
2 1
3

あらためて確認すると一周目で確定した末広町への最短時間を二周目で更新しているのがわかる。

矢印を逆に辿る

最後に末広町から太い矢印を逆に辿っていけば最短ルート「渋谷 → 大崎 → 秋葉原 → 末広町」が求まる。

これまでの図は末広町を目的地としているように見えるが目的地はどこでもよい。

負閉路が起きる原因を確認する

構図

どちらも無限時間かかる。

三軒茶屋から出発

出発地点なので 0 分とする。

次から一周目の繰り返しに入る。

三軒茶屋→神保町

0 + 1 で 1 分かかる。

神保町→三軒茶屋

1 - 2 で -1 分かかる。0 から -1 に更新する。

ここで一周目が終わる。

三軒茶屋 神保町
0
1 -1 1

二周目はもうない。繰り返しは最大「街の数 - 1」で充分だから。でも物足りない。

あえて二周目以降を繰り返す

五周目まで実行した結果

三軒茶屋 神保町
0
1 -1 1
2 -2 0
3 -3 -1
4 -4 -2
5 -5 -3

ここからわかるのは三茶から神保町に行くまでの時間より神保町からいったん三茶までUターンしてから再度神保町に行った方が速く着くを繰り返しているということ。これではいつまでたっても収束しない。

ループ状態に入っているのは太い矢印がお互いを指していることからもわかる。

コード

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

distance = Hash.new(Float::INFINITY)
predecessor = {}

distance["渋谷"] = 0

G.size.times do |i|         # 「節の数」回数
  updated = false
  G.each do |vertex, edges|
    edges.each do |neighbour, weight|
      alt = distance[vertex] + weight
      if alt < distance[neighbour]
        if i == G.size.pred
          raise "負閉路あり"
        end
        distance[neighbour] = alt
        predecessor[neighbour] = vertex
        updated = true
      end
    end
  end
  unless updated
    break
  end
end

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

コードの要点

隣町までより速く行けるなら所要時間を更新する

G.each do |vertex, edges|
  edges.each do |neighbour, weight|
    alt = distance[vertex] + weight
    if alt < distance[neighbour]
      distance[neighbour] = alt
      predecessor[neighbour] = vertex
    end
  end
end

これを「街の数 - 1」だけ繰り返す。この過程をリラクゼーションという。

負閉路の検出方法

リラクゼーションに似た処理を再度行って更新が発生しそうになったら負閉路があるのがわかる。

G.each do |vertex, edges|
  edges.each do |neighbour, weight|
    alt = distance[vertex] + weight
    if alt < distance[neighbour]
      # 負閉路が起きている
    end
  end
end

コードを共通化するには？

  1. リラクゼーションを「街の数」回数繰り返す
  2. 最後のループのときに更新が発生したら負閉路が起きていることがわかる

簡単に言えば余分にリラクゼーションを行ってついでに負閉路検出するということ。これで負閉路の検出コードを別に書かなくてよくなる。とはいえなんでも共通化した方がいいわけでもないので状況に応じて使い分ける。

経路を逆に辿る

普通に書くとこんな感じになるが、

def route_to(vertex)
  routes = []
  while vertex
    routes << vertex
    if vertex == source
      break
    end
    vertex = predecessor[vertex]
  end
  routes.reverse
end

再帰を使うととてもシンプルになり reverse すらいらなくなる。

def route_to(vertex)
  if vertex
    [*route_to(predecessor[vertex]), vertex]
  end
end

route_to("末広町")  # => ["渋谷", "大崎", "秋葉原", "末広町"]

過去問

問題 考察
ABC061 D - Score Attack LINK
ABC137 E - Coins Respawn LINK

Discussion