Floyd-Warshall Algorithm: Get Shortest Paths
Suppose the graph is represented by an adjacency matrix of size n x n
. I know how to get the shortest path matrix for all pairs. But I'm wondering if there is a way to trace all the shortest paths? Blow is a python code implementation.
v = len(graph)
for k in range(0,v):
for i in range(0,v):
for j in range(0,v):
if graph[i,j] > graph[i,k] + graph[k,j]:
graph[i,j] = graph[i,k] + graph[k,j]
source to share
You have to add a new matrix to the if statement to store the path recovery data (an array p
that is the predecessor matrix):
if graph[i,j] > graph[i,k] + graph[k,j]:
graph[i,j] = graph[i,k] + graph[k,j]
p[i,j] = p[k,j]
At the beginning, the matrix p
should be filled as:
for i in range(0,v):
for j in range(0,v):
p[i,j] = i
if (i != j and graph[i,j] == 0):
p[i,j] = -30000 # any big negative number to show no arc (F-W does not work with negative weights)
To restore the path between the nodes i
and j
that you have to call:
def ConstructPath(p, i, j):
i,j = int(i), int(j)
if(i==j):
print (i,)
elif(p[i,j] == -30000):
print (i,'-',j)
else:
ConstructPath(p, i, p[i,j]);
print(j,)
And a test with the function above:
import numpy as np
graph = np.array([[0,10,20,30,0,0],[0,0,0,0,0,7],[0,0,0,0,0,5],[0,0,0,0,10,0],[2,0,0,0,0,4],[0,5,7,0,6,0]])
v = len(graph)
# path reconstruction matrix
p = np.zeros(graph.shape)
for i in range(0,v):
for j in range(0,v):
p[i,j] = i
if (i != j and graph[i,j] == 0):
p[i,j] = -30000
graph[i,j] = 30000 # set zeros to any large number which is bigger then the longest way
for k in range(0,v):
for i in range(0,v):
for j in range(0,v):
if graph[i,j] > graph[i,k] + graph[k,j]:
graph[i,j] = graph[i,k] + graph[k,j]
p[i,j] = p[k,j]
# show p matrix
print(p)
# reconstruct the path from 0 to 4
ConstructPath(p,0,4)
Output:
R
[[ 0. 0. 0. 0. 5. 1.]
[ 4. 1. 5. 0. 5. 1.]
[ 4. 5. 2. 0. 5. 2.]
[ 4. 5. 5. 3. 3. 4.]
[ 4. 5. 5. 0. 4. 4.]
[ 4. 5. 5. 0. 5. 5.]]
Path 0-4:
0 1 5 4
source to share