By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,818 Members | 1,223 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,818 IT Pros & Developers. It's quick & easy.

Calculating Distance From Start Node - Dijkstra's Algorithm

P: 2
Hello,

I am having some trouble in working out the distance of each node from the starting node in my Dijkstra Algorithm code. Here is my code with the section i'm stuck on in bold:

Expand|Select|Wrap|Line Numbers
  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())
I've no idea on where I am going wrong, i've tried a few things now but nothing seems to work
Mar 8 '11 #1
Share this Question
Share on Google+
1 Reply


Expert 100+
P: 624
You are using currentNode for two different variables.
Expand|Select|Wrap|Line Numbers
  1. def tentativeDistance(currentNode, nodeTable):
  2.     # and
  3.     for currentNode in nodeTable: 
Print the values so you know what they are. For example:
Expand|Select|Wrap|Line Numbers
  1. print "startNode =", startNode, type(startNode)
  2. print "currentNode =", currentNode, type(currentNode)
  3. #
  4. #Node[currentNode].distFromSource + 
  5. #      currentDistance = startNode + currentNode 
Perhaps a dictionary of classes would be easier to understand than a list of classes.
Expand|Select|Wrap|Line Numbers
  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() 
Mar 8 '11 #2

Post your reply

Sign in to post your reply or Sign up for a free account.