Dijkstra Algorithm Help
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 = 100
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
--
http://mail.python.org/mailman/listinfo/python-list
Re: Dijkstra Algorithm Help
On Mar 8, 6:49 pm, MRAB wrote:
> 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 = 100
> > 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
--
http://mail.python.org/mailman/listinfo/python-list
Passing Functions
Hi,
I am having an issue with passing values from one function to another
- I am trying to fill a list in one function using the values
contained in other functions as seen below:
infinity = 100
invalid_node = -1
startNode = 0
#Values to assign to each node
class Node:
distFromSource = infinity
previous = invalid_node
visited = False
#read in all network nodes
def network():
f = open ('network.txt', 'r')
theNetwork = [[int(node) for node in line.split(',')] for line in
f.readlines()]
print theNetwork
return theNetwork
#for each node assign default values
def populateNodeTable():
nodeTable = []
index = 0
f = open('network.txt', 'r')
for line in f:
node = map(int, line.split(','))
nodeTable.append(Node())
print "The previous node is " ,nodeTable[index].previous
print "The distance from source is
" ,nodeTable[index].distFromSource
index +=1
nodeTable[startNode].distFromSource = 0
return nodeTable
#find the nearest neighbour to a particular node
def nearestNeighbour(currentNode, theNetwork):
nearestNeighbour = []
nodeIndex = 0
for node in nodeTable:
if node != 0 and currentNode.visited == false:
nearestNeighbour.append(nodeIndex)
nodeIndex +=1
return nearestNeighbour
if __name__ == "__main__":
nodeTable = populateNodeTable()
theNetwork = network()
nearestNeighbour(currentNode, theNetwork, )
So, I am trying to look at the values provided by the network
function, set all nodes to 'visited = false' in populateNodeTable
function and then determine the nodes' nearest neighbour by looking at
the values provided in the previous function, though I get this error
message:
if node != 0 and currentNode.visited == false:
AttributeError: 'int' object has no attribute 'visited'
I'm not sure what to try next
--
http://mail.python.org/mailman/listinfo/python-list
Re: Passing Functions
On Mar 11, 2:00 am, MRAB wrote:
> On 11/03/2011 01:13, yoro wrote:
>
> > Hi,
>
> > I am having an issue with passing values from one function to another
> > - I am trying to fill a list in one function using the values
> > contained in other functions as seen below:
>
> > infinity = 100
> > invalid_node = -1
> > startNode = 0
>
> > #Values to assign to each node
> > class Node:
> > distFromSource = infinity
> > previous = invalid_node
> > visited = False
>
> > #read in all network nodes
> > def network():
> > f = open ('network.txt', 'r')
> > theNetwork = [[int(node) for node in line.split(',')] for line in
> > f.readlines()]
> > print theNetwork
>
> > return theNetwork
>
> > #for each node assign default values
> > def populateNodeTable():
> > nodeTable = []
> > index = 0
> > f = open('network.txt', 'r')
> > for line in f:
> > node = map(int, line.split(','))
> > nodeTable.append(Node())
>
> > print "The previous node is " ,nodeTable[index].previous
> > print "The distance from source is
> > " ,nodeTable[index].distFromSource
> > index +=1
> > nodeTable[startNode].distFromSource = 0
>
> > return nodeTable
>
> > #find the nearest neighbour to a particular node
> > def nearestNeighbour(currentNode, theNetwork):
> > nearestNeighbour = []
> > nodeIndex = 0
> > for node in nodeTable:
> > if node != 0 and currentNode.visited == false:
> > nearestNeighbour.append(nodeIndex)
> > nodeIndex +=1
>
> > return nearestNeighbour
>
> > if __name__ == "__main__":
> > nodeTable = populateNodeTable()
> > theNetwork = network()
> > nearestNeighbour(currentNode, theNetwork, )
>
> > So, I am trying to look at the values provided by the network
> > function, set all nodes to 'visited = false' in populateNodeTable
> > function and then determine the nodes' nearest neighbour by looking at
> > the values provided in the previous function, though I get this error
> > message:
>
> > if node != 0 and currentNode.visited == false:
> > AttributeError: 'int' object has no attribute 'visited'
>
> > I'm not sure what to try next
>
> In nearestNeighbour, 'currentNode' is an int because that's what you're
> passing in ... except that you aren't.
>
> You're passing in the value of the global 'currentNode', which doesn't
> exist. Perhaps you meant 'startNode'?
>
> When I run the above program I get:
>
> Traceback (most recent call last):
> File "C:\Documents and Settings\Administrator\Desktop\network.py",
> line 49, in
> nearestNeighbour(currentNode, theNetwork, )
> NameError: name 'currentNode' is not defined
I've found the error, I had to type in:
for node in nodeTable:
if node != 0 and Node.visited == False:
--
http://mail.python.org/mailman/listinfo/python-list
