-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathFloydWarshall.py
40 lines (32 loc) · 1.01 KB
/
FloydWarshall.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
inf = 1000000
# Implementation: This algo is O(V^3)
def floydWarshall(graph):
# build shortest-path-trees used in path reconstruction
next = []
for i in range(0, len(graph)):
next.append([])
for i in range(0, len(next)):
for j in range(0, len(graph)):
next[i].append(-1)
next[i][i] = i
for i in range(0, len(graph)):
for j in range(0, len(graph)):
if (graph[i][j] != inf):
next[i][j] = j
dist = graph
for k in range(0, len(graph)):
for i in range(0, len(graph)):
for j in range(0, len(graph)):
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
next[i][j] = next[i][k]
return (dist, next)
def reconstructPath(u, v, next):
""" path reconstruction using shortest path tree """
if (next[u][v] == -1):
return []
path = [u]
while (u != v):
u = next[u][v]
path.append(u)
return path