f



find all paths between TWO selected nodes how to ?

Hi group,

Im trying to find all path between two nodes (given a directed
weighted graph G. find all paths between the two given node - say node
b and node f ).
is there any algorithm available specifically for this. or can i
modify dijkstra or floyd.

Note: the problem is not a shortest path problem. i have found huge
number of articles on path finding problem. unfortunately almost
ninety percent of them deal with shortest path problem (or a kind of
shortest path prob) :(
thanks in  advance
javakid
0
fk6k81k02 (1)
6/30/2003 5:37:13 AM
comp.theory 5139 articles. 1 followers. marty.musatov (1143) is leader. Post Follow

1 Replies
486 Views

Similar Articles

[PageSpeed] 49

On 29 Jun 2003, javakid wrote:

> Im trying to find all path between two nodes (given a directed
> weighted graph G. find all paths between the two given node - say node
> b and node f ).
> is there any algorithm available specifically for this. or can i
> modify dijkstra or floyd.

  You won't find a polynomial-time algorithm for this, simply because 
there can be exponentially many paths between two nodes.
  What you want to learn about are backtracking (exhautive) search 
algorithms.

Jim

0
nastos (149)
6/30/2003 7:20:51 AM
Reply: