最短経路を求める３つのアルゴリズム

蟻本の2-5節を読んで最短経路を求める方法を学んだのでまとめです。

1 ベルマン・フォード法

ある一点から全ての点への最短距離を求める方法の一つ。辺一つ一つについて、辺の向き先の点へのスタート地点からの距離が短く更新できないかを何回も繰り返し見ていく。負の閉路がなければ、辺の数を|V|として|V|-1回で収束する。逆に、|V|-1回で収束しない場合は負の経路があるということなので、負の経路の検出にも使える。計算量はO(V^2)。

Edge = namedtuple('Edge', ('fr', 'to', 'cost'))

def bellman_ford(n, start, edges):
    dists = [inf for _ in range(n)]
    dists[start] = 0
    while True:
        updated = False
        for e in edges:
            if dists[e.fr] != inf and dists[e.fr] + e.cost < dists[e.to]:
                updated = True
                dists[e.to] = dists[e.fr] + e.cost

        if not updated:
            break

    return dists

2 ダイクストラ法

ある一点から全ての点への最短距離を求める方法の一つ。最短距離を確定している点を一つ一つ増やしていく方法。最初、スタート地点への距離が0で、これが最短ということがわかっている。スタート地点と直接繋がっている点について、それぞれ仮の最短距離をスタート地点と繋がっている辺の長さとする。このうち、仮の最短距離がもっとも短い点については、それが真の最短距離であると確定できるので確定し、その点と繋がっている点について仮の最短距離を更新...ということを繰り返していく。最短距離がもっとも短い点を選び出す処理に優先度付きキューを使うと、計算量はO(E logV)とベルマンフォードよりも小さくなる。

def dijkstra(n, start, costs):
    dists = [inf for _ in range(n)]
    dists[start] = 0

    queue = []
    for (i, d) in enumerate(dists):
        heapq.heappush(queue, (d, i))

    while len(queue) > 0:
        d, i = heapq.heappop(queue)
        if d > dists[i]:
            continue

        for v in range(n):
            if v == i or costs[i][v] == inf:
                continue

            if dists[i] + costs[i][v] < dists[v]:
                dists[v] = dists[i] + costs[i][v]
                heapq.heappush(queue, (dists[v], v))

    return dists

3 ワーシャルフロイド法

全ての点から全ての点への最短距離を求める方法の一つ。dp[k][i][j]を0 - kの点のみを使ったiからjの最短距離として、dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])という漸化式で更新していく。計算量はO(E^3)。実装が単純なので、計算量に余裕があるならば、一点からの最短距離しか必要でない場合にも使うと良い。

def warshall_floyd(n, costs):
    dists = [[costs[i][j] for j in range(n)] for i in range(n)]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j])

    return dists