Python - Dijsktra的算法距離問題

Question

我遇到了我的代碼問題，我無法計算從起始節點到節點的距離。我有以下形式的文本文件：

1,2,3,4,5,6,7,8,9

1,2,3,4,5,6,7,8， 9

這表示圖中的節點距離。不幸的是，儘管嘗試了幾種不同的方法，但我仍然不斷地提出各種錯誤消息，這裏是我的代碼。

infinity = 1000000 
invalid_node = -1 
startNode = 0 

class Node: 
     distFromSource = infinity 
     previous = invalid_node 
     visited = False 

def populateNodeTable(): 
    nodeTable = [] 
    index =0 
    f = open('route.txt', 'r') 
    for line in f: 
     node = map(int, line.split(',')) 
     nodeTable.append(Node()) 
     print nodeTable[index].previous 
     print nodeTable[index].distFromSource 
     index +=1 

    nodeTable[startNode].distFromSource = 0 

    return nodeTable 

def tentativeDistance(currentNode, nodeTable): 
    nearestNeighbour = [] 
    for currentNode in nodeTable: 
#  if Node[currentNode].distFromSource + currentDistance = startNode + currentNode 
#  currentDistance = currentNode.distFromSource + nodeTable.currentNode 
     currentNode.previous = currentNode 
     currentNode.length = currentDistance 
     currentNode.visited = True 
     currentNode +=1 
     nearestNeighbour.append(currentNode) 
     print nearestNeighbour 

    return nearestNeighbour 

def shortestPath (nearestNeighbour) 
    shortestPath = [] 
    f = open ('spf.txt', 'r') 
    f.close() 

currentNode = startNode 

if __name__ == "__main__": 
    populateNodeTable() 
    tentativeDistance(currentNode,populateNodeTable()) 

在我的tentativeDistance函數中以'＃'開頭的行是給我帶來麻煩的部分。我已經在網上看了一些其他的實現，雖然他們讓我困惑

Answer 1

幾個月前，我一直在Python編程Dijkstra的算法;它的測試，它應該工作：

def dijkstra(u,graph): 
    n = graph.numNodes 
    l = { u : 0 } ; W = graph.V() 
    F = [] ; k = {} 
    for i in range(0,n): 
     lv,v = min([ (l[lk],lk) for lk in l.keys() if lk in W ]) 
     W.remove(v) 
     if v!=u: F.append(k[v]) 
     for v1 in [ v2 for v2 in graph.G(v) if v2 in W ]: 
     if v1 not in l or l[v]+graph.w(v,v1) < l[v1]: 
      l[v1] = l[v] + graph.w(v,v1) 
      k[v1] = (v,v1) 
    return l,F 

你需要一個類圖與方法V（）（它產生的圖形節點），W（V1，V2）（它產生的邊的權重（V1，V2 ）），刪除（從圖中刪除一條邊）和屬性numNodes（產生圖中節點的數量）和G（v），產生節點v的鄰域