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
+ 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 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   currentNode = startNode   if __name__ == "__main__":     populateNodeTable()     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
1 Reply

 Expert 100+ P: 624 You are using currentNode for two different variables. Expand|Select|Wrap|Line Numbers def tentativeDistance(currentNode, nodeTable):     # and     for currentNode in nodeTable:  Print the values so you know what they are. For example: Expand|Select|Wrap|Line Numbers print "startNode =", startNode, type(startNode) print "currentNode =", currentNode, type(currentNode) # #Node[currentNode].distFromSource +  #      currentDistance = startNode + currentNode  Perhaps a dictionary of classes would be easier to understand than a list of classes. Expand|Select|Wrap|Line Numbers class Node:     def __init__(self, previous):        infinity = 1000000        invalid_node = -1        self.distFromSource = infinity        self.previous = previous        self.visited = False     def populateNodeTable():      startNode = 0     ## dictionary with key = record or node number     nodeTable = {} ##    f = open('route.txt', 'r')     f = range(10)     ## test data     for index, line in enumerate(f):          nodeTable[index] = Node(index-1)      ## index-1 = previous record     nodeTable[startNode].distFromSource = 0     nodeTable[startNode].previous = -1       ## print ascending     for node in range(0, len(nodeTable)):         ## add to distFromSource         nodeTable[node].distFromSource += node         print node, nodeTable[node].distFromSource       ## print descending using another method     print "-"*30     index = 9     ## last node number      while index > -1:         print index, nodeTable[index].distFromSource, \               "previous =", nodeTable[index].previous         index = nodeTable[index].previous     populateNodeTable()  Mar 8 '11 #2

### Post your reply

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