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() 的类 Graph（生成图节点）、w(v1,v2)（生成边的权重 (v1,v2)）、remove（删除图中的一条边）和属性 numNodes（生成图中的节点数）和 G(v)，生成节点 v 的邻域。