breadth first search

[Tim Chase]

> Thanks for your reply and the structure of the file structure going to be
> read is
> 
> <total number of nodes>
> <first node><second node><distance from first node to second node>
> ...
> <end of file represented by -1>
> 
> The aims is to find out the shortest path(s) for the leaf node(s)
> 
> Example:
> 9
> 0 1 1
> 0 4 2
> 1 2 3
> 1 3 4
> 4 3 2
> 4 5 1
> 4 8 2
> 5 6 2
> 5 7 2
> -1
> 
> Output:
> Possible solutions:
> Path=0,1,2 length=4
> Path=0,4,3 length=4

Well, I notice several items here:

1)  the number of records is obvious, as you have newlines
2)  the end-of-file is obvious to Python
3)  you don't explicitly spell out which nodes are availble 
leaf-nodes

To build a tree like your data provides, you might have some code 
like

data = open("data.txt","r")
lines = [line[:-1] for line in data.readlines()[1:-1]]
data.close()
graph = {}
for line in lines:
     a,b,weight = line.split(" ",2)
     weight = int(weight)
     if a in graph:
         graph[a][b] =(weight)
     else:
         graph[a] = {b:weight}

print repr(graph)

You can then navigate this graph/tree.  Starting at the root node:

	root = graph("0")

root now contains a dictionary.  The keys in this dictionary 
specify which nodes can be reached from the current location, and 
the values of the dictionary represent the weight/cost associated 
with traversing to this node.

You can then do a breadth-first search of this data structure 
just as you would in any other language.  It doesn't look like it 
would be a straight-forward breadth-first search, as it looks 
like you want to take the weight into account as well as the 
number of steps from the root.

-tkc

PS:  you should CC the list when you reply, as I certainly don't 
have all the answers, and there are others on the mailing list 
that can point out better ways to do things, have other ideas, or 
be there more predictable than I am (otherwise, you may mail 
something and I might not get it for a week)