Floyd-Warshallアルゴリズム：最短経路を得る

Question

グラフがn x n次元隣接行列で表されるとします。私はすべてのペアの最短経路行列を得る方法を知っています。しかし、私はすべての最短経路を辿る方法があるのだろうか？ BlowはPythonコードの実装です。

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のように満たされなければなら開始時：

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

あなたは、パスの再構成データ（前身行列をある配列p）を格納するためにあなたのif文新しい行列に追加する必要があります：あなたが呼び出す必要がありiとjノード間のパスを再構築するために

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) 

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) 

出力：

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

パス0-4：

0 
1 
5 
4