Pythonでアルゴリズム（ダイクストラ法,Dijkstra）

はじめに

　今までは貼るだけだったライブラリの中身を少しずつ勉強していきたい所存。この記事を書く理由は、自分の考えの確認とアドバイスなどをいただきたいからなので是非コメントお願いします!(特に高速化、計算量)

目的

　負のコストの辺がないグラフについて、ある1つの始点からの他の頂点への最短距離を求める。(単一始点最短路)

原理

　グラフの頂点数が$V$,辺の数が$E$である時を考える。まずは2つのリストを用意する。1つは始点からの最短距離を記録するもの、もう1つは最短路が確定したかどうかを記録するものである。(1つにまとめることもできそうですが、理解する時と同じようにします。)ここで、自身の点への距離は0で確定、他の点への距離はINFとする。
　辺のコストに関して最小値を取り出すための優先度付きキューを用意する。そして、自身の点から伸びている辺を優先度付きキューに入れる。このとき、コストが最小値である辺の行く先に関して、他の辺を経由してより少ないコストになることはない。なぜなら、コストは非負であるから遠回りすることになるからだ。
　ということで、コストが最小値となる辺を取り出し、この行先の頂点への最短距離を確定する。さらに、この頂点から伸びる辺についても同様に優先度付きキューに入れていく。距離はこの頂点までの距離+辺のコスト。ここで、最短距離が確定している行先をもつ辺に関しては最短距離に関わることはないので、入れないようにすると計算量が軽くなる。
　上の作業をすべての最短距離が確定するまで繰り返す。(実装では優先度付きキューが空になるまでにしています)

実装

import heapq
def dijkstra(s):
    # 始点から各頂点への最短距離
    d = [float('inf')]*n
    d[s] = 0
    # 各頂点が訪問済みかどうか
    used = [False]*n
    used[s] = True
    # 仮の距離を記録するヒープ
    que = []
    for e in g[s]:
        heapq.heappush(que, e)
    while que:
        u, v = heapq.heappop(que)
        if used[v]:
            continue
        d[v] = u
        used[v] = True
        for e in g[v]:
            if not used[e[1]]:
                heapq.heappush(que, [e[0] + d[v], e[1]])
    return d

入力

n = 4
g = [[[1, 1], [4, 2]], [[1, 0], [2, 2], [5, 3]], [[4, 0], [2, 1], [1, 3]], [[1, 2], [5, 1]]] # 隣接リスト
print(dijkstra(0))

出力

[0, 1, 3, 4]

計算量解析

　優先度付きキューへの追加は辺の数による$O(E)$。優先度付きキューのサイズは、辺を最短距離にならない場合には入れないことにより、$V$に比例となるので各操作は$O(logV)$。よって、計算量は$O(ElogV)$。

疑問

　優先度付きキューのサイズが辺の数$E$に比例かなあと思いましたが枝刈りで$V$に比例するところがちょっと抵抗がありました。具体的に書き出してみるとまあ$E$には到底届かないことは分かるのですが何か数式とかで簡単に表せたら教えてほしいです笑。そもそも辺がすべての頂点間に張られているときなどは$E∝V^2$となり他の$O(V^2)$のアルゴリズムより悪化するので考える必要ない気もしますが!

具体例

　上の例です。到達可能な頂点の中で最小のコストのものを選んで更新していきます。

おわりに

　今後も備忘録として更新していきたいです。たまに記事を参考文献にしてくれることも増えたのでモチベが上がっています。

参考文献

プログラミングコンテストチャレンジブック
じゅっぴーさんのブログ