Dijkstra Algorithm Help

[yoro]

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

 

[MRAB]

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.

 

[yoro]

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

Thanks for replying, maybe i'm misunderstanding your comment -
nodeTable is used to store the distances from source of each node
within a text file, the file having the format :

1,2,3,4,5,6,7,8,9
1,2,3,4,5,6,7,8,9

Each of these nodes will have the same settings as set out in Class
Node, i.e. all having no previous nodes. I am then trying to pass this
parameter to the next function so that the distance from the start
node can be calculated

 

[Dennis Lee Bieber]

Thanks for replying, maybe i'm misunderstanding your comment -
nodeTable is used to store the distances from source of each node
within a text file, the file having the format :

But "nodeTable" ONLY EXISTS as a local name inside the function you
use to populate it... The end of the function is "return nodeTable"
which means the function returns a value... You never SAVE that value to
anything so as soon as the function returns the garbage collector
reclaims the unused "nodeTable" data...

 

[Ulrich Eckhardt]

Thanks for replying, maybe i'm misunderstanding your comment -
nodeTable is used to store the distances from source of each node
within a text file, the file having the format :

1,2,3,4,5,6,7,8,9
1,2,3,4,5,6,7,8,9

Each of these nodes will have the same settings as set out in Class
Node, i.e. all having no previous nodes.

The thing he tried to point out is that your program is doing things that
make no sense much earlier than where you think your problems lie, and I
tend to agree. If you are reading the file and then discarding what you
read, that just doesn't make sense.

I am then trying to pass this parameter to the next function so that
the distance from the start node can be calculated

You are calling populateNodeTable twice, which already makes no sense. I'd
first try to call this function once and then verify the results by
outputting the content of the node table. Once that is done and the content
is what you would expect it to be, then you can start trying to implement
Dijkstra.

Uli