Re: Question about graph theroy--Help!

Bo wrote:
Hello everyone. I have a question about the graph theroy. The
Dijkstra's algorithm is to find the shortest path from source to
destination. If I want to find all the possible path from the source
to the destination, how should I do?

Thank you very much!

Bo

i'm not a computer scientist, but i'd do an exhaustive search. only possibility that comes to mind. however, there are a few things to take care of (such as loops for example...).

i'd do it perhaps like this:

initialize inode with start node and an empty path leading to it
for every outgoing edge from inode:
initialize a new path with the path leading to \
inode for every outgoing edge and put into pathlist
if the edge already appears in the path-history, \
remove the new path from pathlist (loop)
do the same, if the new node already appeared
append the corresponding edges and nodes.
if the last node in the path is the end-node and put path \
into endpathlist. remove the path from pathlist
if there could be no new paths generated (dead end) \
just remove path from pathlist
go into recursion for every new path in pathlist.
end


again, i'm no computer scientist. someone more versed in graph theory might give you a better or more concise answer...

michael
.