[Tutor] Breadth first search

[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.

Nicky.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.python.org/pipermail/tutor/attachments/20060209/4ec0041d/attachment.html