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的邻域