> 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) -- http://mail.python.org/mailman/listinfo/python-list