ダイクストラ法
概略
幅優先探索ではキューを用いたところを優先度付キュー(heapq)を用いた高速化version。
考え方はこの記事がとてもよくわかる。
https://qiita.com/zk_phi/items/d93f670544e4b9816ed0
結局、辺に重みがあってもその分勝手に一本道の頂点を増やして全ての辺の重みを1に揃えてあげれば幅優先探索が使えるので、重み付きでも考え方は大きく変わらない。
BFSで頑張ってもいいが、重み次第では時間がかかるので一本道を一気に進める様にヒープを用いたダイクストラ法を使って解くといった具合。
テンプレート
import heapq
INF = 10 ** 9
# ----------------------------------------------------------------
# Input
# 1. タプル(重み, 行先)の二次元配列(隣接リスト)
# 2. 探索開始ノード(番号)
# Output
# スタートから各ノードへの最小コスト
# ----------------------------------------------------------------
def dijkstra(edges: "List[List[(cost, to)]]", start_node: int) -> list:
hq = []
heapq.heapify(hq)
# Set start info
dist = [INF] * len(edges)
heapq.heappush(hq, (0, start_node))
dist[start_node] = 0
# dijkstra
while hq:
# ------------------------------------------- タイミング1
min_cost, now = heapq.heappop(hq)
# ------------------------------------------- タイミング2
if min_cost > dist[now]:
continue
for cost, next in edges[now]:
if dist[next] > dist[now] + cost:
dist[next] = dist[now] + cost
heapq.heappush(hq, (dist[next], next))
# --------------------------------------- タイミング3
return dist
実際の動き
テンプレートの上記1~3の各タイミングでのグラフとキューの状態を以下グラフを題材にダイクストラ法の動きを見ていく。始点を0、終点を5として最短経路を導き出す。
計算量
heapqの出し入れ : 1件につきlog(n)
→ popは頂点分で最大n回、pushは辺の分で最大e回なのでO((n+e)logn)
このため、e= n^2の完全グラフでは効率が悪くなる。
https://www-ui.is.s.u-tokyo.ac.jp/~takeo/course/2007/algorithm/dijkstra.pdf
https://www.ioi-jp.org/joi/2007/2008-yo-prob_and_sol/2008-yo-t6/review/2008-yo-t6-review.html
ベルマンフォード法
概略
ダイクストラは負の重みがある辺が存在する場合には利用できない。
ベルマンフォード法では、その時点で確定しているノードのコストを正としてそれぞれのノードから移動可能なノードのコストを決めていく。
当然、既に評価したノードのコストを更新したことでそのノードを正として算出したノードのコストを再計算しないといけないケースが出てくる。
そのため、ベルマンフォード法では全頂点からスタートを除いた(V-1)回まで、更新がある限りこの一連の処理を繰り返す。
ただし、負閉路を含む場合、この更新は無限に終わらない。そのため、(V-1)回の更新に到達しても更新が終わらない場合は負閉路が含まれると判断できる。
テンプレート
INF = 10 ** 16
# ----------------------------------------------------------------
# Input
# 1. 辺のリスト: タプル(始点, 終点, 重み)
# 2. 頂点数
# 3. 探索開始ノード(番号)
# Output
# リスト(スタートから各ノードへの最小コスト。ただし負閉路から到達可能なノードは-INF)
# Note
# 始点から到達不可能な負閉路の有無： × (ベルマンフォード法では発見されない)
# 始点から到達可能だが終点に影響ない負閉路の有無： ○ (出力のリストに-INFが含まれるかどうか)
# 始点から到達可能で終点に到達する負閉路の有無： ○ (出力のリストの終点へのコストが-INFかどうか)
# ----------------------------------------------------------------
def bellmanFord(edges: "List[(from, to, to)]", vertex: int, start_node: int) -> list:
# Initialize
costs = [INF] * vertex
costs[start_node] = 0
for i in range(vertex * 2): # ---- 外側のLoop
for f, t, c in edges: # ---- 内側のLoop
# ------------------------------------------- タイミング1
if costs[f] != INF and costs[t] > costs[f] + c:
if i >= vertex - 1:
costs[t] = -INF
else:
costs[t] = costs[f] + c
return costs
実際の動き
■ 負閉路なしケース
同じく以下の題材において、上記テンプレートの外側ループと内側ループそれぞれのタイミング1のグラフの状態を示す。なお、edgesには辺のコストが小さいものから順に入っていたと仮定する(この順序はなんでもよい)。
最大でも頂点数分ループを回せば全ての頂点のコストが確定する。
■ 負閉路あり(終点に到達する)ケース
負の辺を含む場合にベルマンフォード法が有効なため、題材を以下に変えてみる。
ただし、負閉路があると答えは必ず-∞かというとそうでもない。次の例をみる。
■ 負閉路あり(終点に到達しない)ケース
この場合、負閉路があるもののゴールに繋がらないため影響しない。即ち、ゴールの値はループを回し続けても変化しない。このことを利用して、以下のように頂点数を超えても終点の更新があるかで判断できそうである。
{頂点数}回更新した後にゴールが更新される ＝ 負閉路がある
〃 されない ＝ 負閉路があったとしても影響しない
しかし、これは次のような例では成立しない。次の例をみる。
■ 負閉路あり(コストが莫大な辺がある)ケース
負閉路を1周回る毎にコストが -3 になるので、いつかは終点の値を更新するだろうが、それは頂点数6回だけ回しても訪れないため判断を誤る。
そのため、前述のコードは頂点数の2倍分ループを回し、以下の処理が入っている。
if i >= vertex - 1:
costs[t] = -INF
{頂点数}回を超えてからのループでは更新があったらそこを-∞に書き換える。
この負閉路から到達可能な箇所を-∞で書き換える処理を同じく{頂点数}回行うと正しい影響範囲がわかる
計算量
O(VE)。
例題
ダイクストラ法
1. Single Source Shortest Path
import heapq
INF = 10 ** 9
def main():
V, E, r = map(int, input().split())
edge = [[] for _ in range(V)]
costs = []
for _ in range(E):
s, t, d = map(int, input().split())
edge[s].append((d, t))
dist = dijkstra(edge, r)
for c in dist:
print("INF" if c == INF else c)
if __name__ == '__main__':
main()
2. 第７回日本情報オリンピック 予選 F - 船旅
import heapq
INF = 10 ** 9
def main():
n, k = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(k):
i = list(map(int, input().split()))
if i[0] == 1:
edge[i[1] - 1].append((i[3], i[2] - 1))
edge[i[2] - 1].append((i[3], i[1] - 1))
else:
costs = dijkstra(edge ,i[1] - 1)
print(-1 if costs[i[2] - 1] == INF else costs[i[2] - 1])
return
if __name__ == '__main__':
main()
3. ABC079 D - Wall
import heapq
INF = 10 ** 9
def main():
H, W = map(int, input().split())
edges = [[] for i in range(10)]
for i in range(10):
c = list(map(int, input().split()))
for j in range(10):
if i == j:
continue
edges[i].append((c[j], j))
nums = [0] * 10
for _ in range(H):
A = list(map(int, input().split()))
for a in A:
if a == -1:
continue
nums[a] += 1
ans = 0
for i, s in enumerate(nums):
if i == 1:
continue
dist = dijkstra(edges, i)
ans += dist[1] * s
print(ans)
if __name__ == '__main__':
main()
ベルマンフォード法
1. Single Source Shortest Path (Negative Edges)
INF = 10 ** 9
def main():
V, E, r = map(int, input().split())
edges = []
for _ in range(E):
s, t, d = map(int, input().split())
edges.append((s, t, d))
costs = bellmanFord(edges, V, r)
if -INF in costs:
print("NEGATIVE CYCLE")
return
for c in costs:
print("INF" if c == INF else c)
if __name__ == '__main__':
main()
2. ABC061 D - Score Attack
INF = 10 ** 16
def main():
N, M = map(int, input().split())
edges = []
costs = []
for _ in range(M):
a, b, c = map(int, input().split())
edges.append((a - 1, b - 1, -c))
costs = bellmanFord(edges, N, 0)
if costs[-1] == -INF:
print("inf")
return
print(-costs[N - 1])
return
if __name__ == '__main__':
main()
3. ABC137 E - Coins Respawn
最大値を求める問題でもコストを全てマイナスにして実施することで対応できる。
def main():
N, M, P = map(int, input().split())
edges = []
for _ in range(M):
a, b, c = map(int, input().split())
edges.append((a - 1, b - 1, -(c - P)))
costs = bellmanFord(edges, N, 0)
if costs is None or costs[-1] == -INF:
print(-1)
return
print(0 if costs[N - 1] > 0 else -costs[N - 1])
return
if __name__ == '__main__':
main()
参考
ダイクストラ法
ベルマンフォード法