優先度付きキュー(二分ヒープ)と隣接リストを使ったダイクストラ法(Python3)

ダイクストラ法については各自参照してください。この記事では実装のみ取り扱います

螺旋本(P309~314)の「優先度付きキューを用いたダイクストラ法」の実装をしたので、それについてソースコードと一緒に書いていきます

提出リンク

実行時間	メモリ使用量	コード長
2450[ms]	90060[kb]	922[b]

ソースコード(関数部分のみ)

from heapq import heapify, heappush, heappop

inf = float("inf")
def dijkstra(graph, start):  # graphは隣接リスト
    vsize = len(graph)
    dist = [inf] * vsize  # 始点からの最短距離 
    seen = [False] * vsize
    pq = []
    heapify(pq)

    dist[start] = 0
    heappush(pq, (0, start))  # heapではtuple[0]で比較されるのでこの順番で追加する
    while pq:
        cost, u = heappop(pq)
        seen[u] = True
        if dist[u] < cost:
            continue
        for v, w in graph[u]:
            temp_cost = dist[u] + w
            if not seen[v] and temp_cost < dist[v]:
                    dist[v] = temp_cost
                    heappush(pq, (dist[v], v))
    return dist

計算量

Pythonのheapqの実装は二分ヒープらしいので、Wikipediaを参考にすると、のようです。

経路復元

必要になりそうなのでそのうち書きます

最短全域木を根に向かって追っていけばよさそう？