Print all possible routes in a graph between two nodes

[Daniele]

Hi there is a way to put in a struct of vectors all the possibles routes
in a graph from s to d?
Hi thought Dijkstra but I don't know how can i do.

Thanks
Dax

 

[Victor Bazarov]

Hi there is a way to put in a struct of vectors all the possibles
routes in a graph from s to d?
Hi thought Dijkstra but I don't know how can i do.

It is possible because C++ is a language that allows recursive calls
to functions (except 'main').

Declare a vector in which you will try to build a single path. Define
a function to which you will pass the vector under construction and
your collection of vectors (the complete list of routes), and the set
of nodes to exclude. Proceed to enumerate all nodes from current one
while checking against the exclusion set. If you reach your destination
node, add the currently built path to the list and return. If you see
no way ahead (dead end), don't add the currently built path, but still
return. Shouldn't be that difficult.

To be fair to the newsgroup, your question is only marginally related
to the subject of comp.lang.c++. Perhaps you should make an attempt to
code what you think the right algorithm is, and if you encounter any
_language_ problem, come back and post a particular _language_ question.

Victor

 

[Alf P. Steinbach]

* Daniele:

Hi there is a way to put in a struct of vectors all the possibles routes
in a graph from s to d?
Hi thought Dijkstra but I don't know how can i do.

Hi this is off-topic in [comp.lang.c++] as it isn't C++ related.

Hi try [comp.programming], which I have crossposted this to.

Hi follow-up is also set to [comp.programming].

 

[Daniele]

There is a simple example to test it?

Thanks
Daniele

 

[Victor Bazarov]

There is a simple example to test it?

To test what?

And don't top-post please.

 

[Daniele]

To test what?

Do you have a sample in c++ of this algorithm to discover all the paths
from two nodes?

And don't top-post please.

Sorry But I was in late...
But Now I respect the netiquette

Thanks
Daniele

 

[tom_usenet]

Hi there is a way to put in a struct of vectors all the possibles routes
in a graph from s to d?
Hi thought Dijkstra but I don't know how can i do.

Use boost's powerful graph library:
http://www.boost.org/libs/graph/doc/table_of_contents.html

I don't think Dijkstra will do it, and you'll have to decide on your
definition of a "possible route" (i.e. a vertex can be visited only
once in each route, etc.). Working out the actual algorithm is a
question for a maths group.

Tom

 

[Daniele]

Yes I've seen... and now I try to use it...
Dax

 

[Victor Bazarov]

Do you have a sample in c++ of this algorithm to discover all the paths
from two nodes?

Nope. And I think I've described the algorithm well enough for
anybody who's interested to implement it. Not the best of them,
I am certain, but can be made working (like the bubble sort for
sorting). Besides, I am sure that after a few minutes you could
find an implementation of something like it on the Web. Try to
use Google or any other search engine.

BTW, this newsgroup doesn't usually do anybody's homework. Not
that I can say for sure that it's your homework, but just FYI.

V