计算与起始节点的距离-Dijkstra算法

  • 时间:
  • 分类: Python

你好,
我在计算Dijkstra算法代码中每个节点到起始节点的距离时遇到了一些麻烦。以下是我坚持使用粗体的部分的代码：

选择 | 换行 | 行号
  1. infinity = 1000000
  2. invalid_node = -1
  3. startNode = 0
  4.  
  5. class Node:
  6.      distFromSource = infinity
  7.      previous = invalid_node
  8.      visited = False
  9.  
  10. def populateNodeTable(): 
  11.     nodeTable = []
  12.     index =0
  13.     f = open('route.txt', 'r')
  14.     for line in f: 
  15.       node = map(int, line.split(',')) 
  16.       nodeTable.append(Node()) 
  17.       print nodeTable[index].previous 
  18.       print nodeTable[index].distFromSource 
  19.       index +=1
  20.     nodeTable[startNode].distFromSource = 0 
  21.  
  22.     return nodeTable
  23.  
  24. def tentativeDistance(currentNode, nodeTable):
  25.     nearestNeighbour = []
  26.     for currentNode in nodeTable:
  27. #         if Node[currentNode].distFromSource + 
  28.      currentDistance = startNode + currentNode
  29. #      currentDistance = currentNode.distFromSource + nodeTable.currentNode 
  30.          currentNode.previous = currentNode
  31.          currentNode.length = currentDistance
  32.          currentNode.visited = True
  33.          currentNode +=1
  34.          nearestNeighbour.append(currentNode)
  35.          print nearestNeighbour
  36.  
  37.     return nearestNeighbour
  38.  
  39. currentNode = startNode
  40.  
  41. if __name__ == "__main__":
  42.     populateNodeTable()
  43.     tentativeDistance(currentNode,populateNodeTable())

我不知道我哪里错了，我现在试了几种方法，但似乎都不管用

# 回答1


您正在为两个不同的变量使用CurentNode。

选择 | 换行 | 行号
  1. def tentativeDistance(currentNode, nodeTable):
  2.     # and
  3.     for currentNode in nodeTable: 

打印值，以便您知道它们是什么。例如：

选择 | 换行 | 行号
  1. print "startNode =", startNode, type(startNode)
  2. print "currentNode =", currentNode, type(currentNode)
  3. #
  4. #Node[currentNode].distFromSource + 
  5. #      currentDistance = startNode + currentNode 

也许一本班级词典会比一份班级清单更容易理解。

选择 | 换行 | 行号
  1. class Node:
  2.     def __init__(self, previous):
  3.        infinity = 1000000
  4.        invalid_node = -1
  5.        self.distFromSource = infinity
  6.        self.previous = previous
  7.        self.visited = False
  8.  
  9.  
  10. def populateNodeTable(): 
  11.     startNode = 0
  12.     ## dictionary with key = record or node number
  13.     nodeTable = {}
  14. ##    f = open('route.txt', 'r')
  15.     f = range(10)     ## test data
  16.     for index, line in enumerate(f): 
  17.         nodeTable[index] = Node(index-1)      ## index-1 = previous record
  18.     nodeTable[startNode].distFromSource = 0
  19.     nodeTable[startNode].previous = -1
  20.  
  21.     ## print ascending
  22.     for node in range(0, len(nodeTable)):
  23.         ## add to distFromSource
  24.         nodeTable[node].distFromSource += node
  25.         print node, nodeTable[node].distFromSource
  26.  
  27.     ## print descending using another method
  28.     print "-"*30
  29.     index = 9     ## last node number 
  30.     while index > -1:
  31.         print index, nodeTable[index].distFromSource, \
  32.               "previous =", nodeTable[index].previous
  33.         index = nodeTable[index].previous
  34.  
  35.  
  36. populateNodeTable() 

标签: python

添加新评论