Dijkstra
コードについての説明
非負重みの辺のみからなるグラフに対する単一始点最短経路問題(SSSP) を効率よく解くアルゴリズム.
始点からの距離が近いものから順に探索を繰り返す("始点から最も近い頂点"は優先度付きキューを用いて効率よく管理する).
ここでヒープとして二分ヒープではなくフィボナッチヒープを用いると, $\O ((m + n) \log n) \rightarrow \O (n \log n + m)$ になる(参考).
また二分ヒープのかわりに Radix Heap を用いた Dijkstra 法の高速化の話もある(参考).
密なグラフ($m = \Theta (n^2)$) については優先度付きキューを使わず一番近い頂点を愚直に計算することで $\O (n^2)$ で解くことができる.
正の整数の重みの辺からなる無向グラフについては単一始点最短経路問題が線形時間で解けることが知られている.
"Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time" [Thorup 1997]
(関数)
add_edge$(st, ed, cost)$ : $st$ から $ed$ に向かう重み $cost$ の有向辺を追加する
solve$(start)$ : start を始点として各頂点までの最短距離を求める
時間計算量: $\O ((n + m) \log n)$
コード
from heapq import heappush, heappop
class Dijkstra:
class Edge:
def __init__(self, end, cost):
self.to = end
self.cost = cost
def __init__(self, node_size, inf):
self._node = node_size
self._graph = [[] for _ in range(self._node)]
self.inf = inf
self.dist = [self.inf for _ in range(self._node)]
def add_edge(self, st, ed, cost):
self._graph[st].append(self.Edge(ed, cost))
self._graph[ed].append(self.Edge(st, cost))
def solve(self, start):
que = []
self.dist[start] = 0
heappush(que, (0, start))
while que:
cur_cost, cur_vertex = heappop(que)
if self.dist[cur_vertex] < cur_cost:
continue
for e in self._graph[cur_vertex]:
if self.dist[e.to] > cur_cost + e.cost:
self.dist[e.to] = cur_cost + e.cost
heappush(que, (self.dist[e.to], e.to))