Breadth first problem

[Nicky Ng]

Hi,

I would like to implement a breadth first serach with Python and read data from a text file with following file format

File structure description
First line contains number of node
Second line contains node id(s) and distance between node id
Last line is -1
<number of node>
<N1><N2><W1>  Each node or distance is separated by space
-1

For the example below, first line represent number of node is 10, second line contains first node id 0, second node id 1, distance between node id 0 and node id 1 is 2

0 is the root (starting node), the aim of the searching program is to find out the shortest path from 0 to a leaf node and print out the node path and value the path distance

Could you give me any idea how to implement this search program with Python?

Example:
10
0 1 2
0 5 3
1 2 2
1 3 4
2 1 3
2 3 1
5 6 3
5 7 1
6 8 1
7 8 1
7 9 2
9 5 3
-1

Outcome:
Possible solution:
Path=0,1,2,3 length=5
Path=0,5,6,8 length=5
Path=0,5,7,8 length=5

Thank you for your help.

I attached program part that I implemented, however, I am not sure what's wrong of the program logic that I cannot get the correct answer.

Nicky.

If you have any idea, could you please reply me at nickyncy at yahoo.com.hk
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20060209/7e9b703c/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tes3
Type: application/octet-stream
Size: 2544 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/python-list/attachments/20060209/7e9b703c/attachment.obj>