Dijkstra Algorithm Help

[MRAB]

On 08/03/2011 18:12, yoro wrote:
> Hello,
>
> I am having a little trouble writing Dijkstra's Algorithm, at the
> point where I have to calculate the distance of each node from the
> source - here is my code so far:
>
> 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(','))

"node" will be a list of ints, but you're not doing anything with them.

>        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 = + nodeTable[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()

The only effect of "populateNodeTable" is to return a node table, which
is then discarded.

>      tentativeDistance(currentNode,populateNodeTable())
>
> As can be seen from the lines commented out, I have tried a few ways
> of getting the distance though none of them has worked; I am not sure
> on how I can resolve this problem