Floyd Warshall在Python中的實現

Question

我正在嘗試爲加權有向圖實現Floyd Warshall圖算法，但無法使其工作。

僅限於1和0的後續權重。

實現看起來像這樣（儘管我已經從某處執行了實現）。

INF = 999999999 

def printSolution(distGraph): 
    string = "inf" 
    nodes =distGraph.keys() 
    for n in nodes: 
     print "\t%6s"%(n), 
    print " " 

    for i in nodes: 
     print"%s"%(i), 
     for j in nodes: 
      if distGraph[i][j] == INF: 
       print "%10s"%(string), 
      else: 
       print "%10s"%(distGraph[i][j]), 
     print" " 


def floydWarshall(graph): 
    nodes = graph.keys() 

    distance = {} 

    for n in nodes: 
     distance[n] = {} 

     for k in nodes: 
      distance[n][k] = graph[n][k] 

    for k in nodes: 
     for i in nodes: 
      for j in nodes: 
       distance[i][j] = min (distance[i][j], distance[i][k] + distance[k][j]) 
    printSolution(distance) 

if __name__ == '__main__': 
    graph = { u'node_10': { u'node_10': 0, 
       u'node_4': 1, 
       u'node_5': 0, 
       u'node_6': 0, 
       u'node_7': 0, 
       u'node_8': 0, 
       u'node_9': 0}, 
u'node_4': { u'node_10': 0, 
       u'node_4': 1, 
       u'node_5': 1, 
       u'node_6': 0, 
       u'node_7': 0, 
       u'node_8': 0, 
       u'node_9': 0}, 
u'node_5': { u'node_10': 0, 
       u'node_4': 0, 
       u'node_5': 0, 
       u'node_6': 1, 
       u'node_7': 0, 
       u'node_8': 1, 
       u'node_9': 0}, 
u'node_6': { u'node_10': 0, 
       u'node_4': 0, 
       u'node_5': 0, 
       u'node_6': 1, 
       u'node_7': 1, 
       u'node_8': 0, 
       u'node_9': 0}, 
u'node_7': { u'node_10': 0, 
       u'node_4': 0, 
       u'node_5': 0, 
       u'node_6': 0, 
       u'node_7': 1, 
       u'node_8': 1, 
       u'node_9': 0}, 
u'node_8': { u'node_10': 0, 
       u'node_4': 0, 
       u'node_5': 0, 
       u'node_6': 0, 
       u'node_7': 0, 
       u'node_8': 0, 
       u'node_9': 1}, 
u'node_9': { u'node_10': 1, 
       u'node_4': 0, 
       u'node_5': 1, 
       u'node_6': 0, 
       u'node_7': 0, 
       u'node_8': 0, 
       u'node_9': 0}} 

floydwarshall (graph) 

Answer 1

我犯了一個錯誤，我不應該把0的重量。在指定INF而不是0之後，它就像魅力一樣。