在無向圖上使用字典for floyd算法進行圖初始化？

Question

我想知道如何在無向圖上實現floyd。有了這個實施，

for k in graph: 
    for i in graph: 
     for j in graph: 
      if dist[i][k] + dist[k][j] < dist[i][j]: 
       dist[i][j] = dist[i][k] + dist[k][j] 
       pred[i][j] = pred[k][j] 

我能夠得到的鄰接矩陣：

__0 __1 __2 __3 __4 

0| 0 28 38 33 63 

1| inf 0 10 60 44 

2| inf inf 0 50 80 

3| inf inf inf 0 30 

4| inf inf inf inf 0 

這是一個有向圖。這很好，但我希望鄰接矩陣顯示無向圖。根據我的理解，對於無向圖，這些路徑應沿着0對角線進行鏡像，但我不知道如何執行此操作。

我想：

for k in graph: 
    for i in graph: 
     for j in graph: 
      if dist[i][k] + dist[k][j] < dist[i][j]: 
       dist[i][j] = dist[i][k] + dist[k][j] 
       dist[j][i] = dist[i][k] + dist[k][j] 
       pred[i][j] = pred[k][j] 

但我的圖表證明錯了，它看起來像算法正在經歷不必要的邊緣，以獲得所需的頂點。

__0 __1 __2 __3 __4 

0| 0 48 38 93 63 

1| 48 0 110 60 44 

2| 38 110 0 110 80 

3| 93 60 110 0 30 

4| 63 inf 80 inf 0 

Here is the graph我使用：

{0 : {1:28, 3:33}, 
1 : {2:10, 4:44}, 
2 : {3:50}, 
3 : {4:30}, 
4 : {}} 

編輯：這裏是完整的代碼

import ast 

def floyd(graph): 
    dist = {} 
    pred = {} 

    for u in graph: 
     dist[u] = {} 
     pred[u] = {} 

     for v in graph: 
      dist[u][v] = float('INF') 
      pred[u][v] = -1 
      dist[u][u] = 0 
     for z in graph[u]: 
      dist[u][z] = graph[u][z] 
      pred[u][z] = u 

    for k in graph: 
     for i in graph: 
      for j in graph: 
       if dist[i][k] + dist[k][j] < dist[i][j]: 
        dist[i][j] = dist[i][k] + dist[k][j] 

    return dist, pred 

graph = {} 
graph = ast.literal_eval(open("file2.txt").read()) 
print graph 

dist, pred = floyd(graph) 

print " ", 
for j in dist: print "__" + str(j), 
print "\n" 
for i in dist: 
     print str(i) + "|", 
     for v in dist: print " %s" % (dist[i][v]), 
     print "\n" 

Answer 1

我覺得你的問題可以通過只在您的圖形鏡像所有邊緣被固定字典，如：

graph = {0 : {1:28, 3:33}, 
1 : {2:10, 4:44}, 
2 : {3:50}, 
3 : {4:30}, 
4 : {}} 
# Mirror all edges 
for u in graph: 
    for v in graph[u]: 
     if not u in graph[v]: 
      graph[v][u] = graph[u][v] 

這是將輸入設置爲無向圖的最簡單方法（儘管顯然現在如果您編輯/刪除邊緣，您需要更加小心）。當我將此代碼插入代碼時，我得到：

__0__1__2__3__4 

0| 0 28 38 33 63 

1| 28 0 10 60 44 

2| 38 10 0 50 54 

3| 33 60 50 0 30 

4| 63 44 54 30 0