Floyd-Warshall法
Abstract
Floyd-Warshall法は, 非負の辺重み$ wが与えられたネットワーク$ \mathcal{N} = \left((V, E), w \right)に対する全点対間最短経路問題を解くためのアルゴリズム. $ O(|V|^3)time. Explanation
TODO 書く.
Implementation
グラフ構築
Input
グラフの頂点数 N
グラフの各有向辺の始点 init, 終点 end, 重み weight
無向グラフにも対応可能.
Output
グラフの隣接リスト E
Time complexity
$ O(|E|)time.
最短距離の計算
Input
なし
Output
各頂点間の最短距離が入ったリストのリスト dist
dist[s][t]: 頂点 s から頂点 t への最短距離
Time complexity
$ O(|V||E|)time.
最短経路の構成
Input
始点 s
終点 t
Output
s から t への最短経路からなるリスト P
Time complexity
$ O(|V|)time.
code:python
from itertools import product
class FloydWarshall:
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):
INF = float('inf')
self.dist = [INF * self.N for _ in range(self.N)] # distst: the distance of vertex t from s self.prev = [-1 * self.N for _ in range(self.N)] # prevst: the previous vertex of vertex t on a shortest path from s # initialize
for v in range(self.N):
for u, c in self.Ev: self.distvu = c; self.prevvu = v # update
for k in range(self.N):
for i, j in product(range(self.N), repeat=2):
temp = self.distik + self.distkj if self.distij > temp: self.distij = temp; self.previj = self.prevkj for v in range(self.N):
if self.distvv < 0: return None # There exists a negative cycle return self.dist
def shortest_path(self, s, t):
P = []
while True:
P.append(t)
if t == -1: break
elif t == P0: P.append(t); break Verification
References