Dijkstra法
Abstract
Dijkstra法は, 非負の辺重み$ wが与えられたネットワーク$ \mathcal{N} = \left((V, E), w \right)に対する単一始点最短経路問題を解くためのアルゴリズム. ヒープを利用することで, $ O((|E| + |V|) \log |V|)time. Explanation
TODO 書く.
Implementation
グラフ構築
Input
グラフの頂点数 N
グラフの各有向辺の始点 init, 終点 end, 重み weight
weight は非負である必要がある.
無向グラフにも対応可能.
Output
グラフの隣接リスト E
Time complexity
$ O(|E|)time.
最短距離の計算
Input
始点 s
Output
s から各頂点への最短距離が入ったリスト dist
dist[t]: 頂点 s から頂点 t への最短距離
Time complexity
ヒープを利用して, $ O((|E| + |V|) \log |V|)time.
最短経路の構成
Input
終点 t
Output
s から t への最短経路からなるリスト P
Time complexity
$ O(|V|)time.
code:python
from heapq import heappush, heappop
class Dijkstra:
def __init__(self, N):
self.E = [[] for _ in range(N)]
def add_edge(self, init, end, weight, undirected=False):
self.Einit.append((end, weight)) if undirected: self.Eend.append((init, weight)) def distance(self, s):
INF = float('inf')
E, N = self.E, self.N
self.dist = dist = INF * N # the distance of each vertex from s self.prev = prev = -1 * N # the previous vertex of each vertex on a shortest path from s heap = []
heappush(heap, (0, s))
while heap:
d, v = heappop(heap)
if distv < d: continue # (s,v)-shortest path is already calculated temp = d + c
heappush(heap, (temp, u))
n_visited += 1
if n_visited == N: break
return dist
def shortest_path(self, t):
P = []
prev = self.prev
while True:
P.append(t)
if t == -1: break
Verification
References