Python - Dijkstra算法距离问题

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)的权重），remove（这个方法可以从图中移除一条边），还有一个属性numNodes（这个属性可以返回图中节点的数量），以及G(v)（这个方法可以返回节点v的邻居）。