0

我的代码遇到了问题，我无法计算从起始节点到节点的距离。我有一个形式的文本文件：

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 函数中以“#”开头的行是给我带来麻烦的部分。我已经查看了网络上的其他一些实现，尽管它们让我感到困惑

4

1 回答 1

0

几个月前，我一直在用 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 的邻域。

于 2011-03-08T21:08:18.617 回答