Floyd-Warshall算法：得到最短路徑

Question

假設一個圖由n x n維度鄰接矩陣表示。我知道如何獲得所有線對的最短路徑矩陣。但我不知道有沒有辦法追蹤所有最短路徑？ Blow是python代碼的實現。

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] 

Answer 1

你必須添加到您的if語句一個新的矩陣，以存儲路徑重建數據（數組p這是前任矩陣）：

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] 

在開始使用矩陣p都被填上：

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) 

爲了重建i和j節點之間的路徑，你必須調用：

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,) 

並與上述功能測試：

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) 

輸出：

號碼：

[[ 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.]] 

路徑0-4：

0 
1 
5 
4