Assume a graph is represented by a n x n
dimension adjacency matrix. I know the how to get the shortest path matrix for all pairs. But I wonder is there a way to trace all the shortest paths?
Blow is the 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]
You have to add to your if statement a new matrix to store path reconstruction data (array p
which is 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
have to 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 reconstruct the path between i
and j
nodes 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 the test with above function:
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:
p:
[[ 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