Calculating Distance From Start Node - Dijkstra's Algorithm

[Greg Jackson]

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:

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

[dwblas]

You are using currentNode for two different variables.

def tentativeDistance(currentNode, nodeTable):
    # and
    for currentNode in nodeTable: 

Print the values so you know what they are. For example:

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.

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()