DFS will give only one path. You need all paths .. so it would be
something like this :
end_node
path_so_far
FindPaths ( curr_node ) {
if ( curr_node = = end_node ) {
print path_so_far;
return;
}
for each node "new_node" reachable from curr_node {
add new_node to path_so_far;
FindPaths( new_node );
remove new_node from path_so_far;
}
}
main
add start to path_so_far
end_node = end
FindPaths ( start )
-Dhyanesh
On 5/9/06, Nat (Padmanabhan Natarajan) <[EMAIL PROTECTED]> wrote:
> How about a DFS? I guess this is Dhyanesh meant by a recursive solution.
>
>
> On 5/9/06, akshay ranjan <[EMAIL PROTECTED] > wrote:
> >
> > Floyd Warshall, Ford or djikistra's algorithms will solve shortest path
> problems but not find all paths . The soln for this would be recursive(
> brute force aproach)
> >
> >
> >
> > On 5/9/06, Alejandro Narancio <[EMAIL PROTECTED]> wrote:
> > >
> > > You can use the Floyd algorithm.
> > >
> > > Regards,
> > >
> > >
> > > Alejandro
> > >
> > >
> > >
> > > On 5/9/06, Dhyanesh <[EMAIL PROTECTED] > wrote:
> > > >
> > > > The problem does not ask for the *shortest* path. He wants to
> > > > enumerate *all* possible paths between two nodes.
> > > >
> > > > -Dhyanesh
> > > >
> > > > On 5/9/06, Narek Saribekyan <[EMAIL PROTECTED]> wrote:
> > > > >
> > > > >
> > > > > Dhyanesh wrote:
> > > > > > Well if you have a graph of 'n' nodes ... then the number of paths
> can
> > > > > > be n! . And you would need that much time to enumerate all of
> them.
> > > > > >
> > > > > > You can write a recursive algo to do this job.
> > > > > >
> > > > > > -Dhyanesh
> > > > > >
> > > > > > On 5/8/06, david wolf < [EMAIL PROTECTED]> wrote:
> > > > > > >
> > > > > > > Hi,
> > > > > > >
> > > > > > > I have a questions about a directed graph. Given two node k and
> i, I
> > > > > > > wish to enumerate all the paths from node k to node i. How to do
> this?
> > > > > > >
> > > > > > > Can anyone direct me how to do it or maybe give me a url for
> > > > > > > explanation somewhere else?
> > > > > > >
> > > > > > > Also, what is the time complexity for achieving this?
> > > > > > >
> > > > > > > Thanks,
> > > > > > >
> > > > > > > David
> > > > > > >
> > > > > > >
> > > > > > > >
> > > > > > >
> > > > > Dynamic Programming-the answer is in Dijkstra's algorithm.
> > > > >
> > > > > 5.3. Dijkstra Algorithm
> > > > > Taken from:
> > > > >
> http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html
> > > > > Dijkstra's algorithm (invented by Edsger W. Dijkstra) solves the
> > > > > problem of finding the shortest path from a point in a graph (the
> > > > > source) to a destination. It turns out that one can find the
> shortest
> > > > > paths from a given source to all points in a graph in the same time,
> > > > > hence this problem is called the Single-source shortest paths
> problem.
> > > > > This problem is related to the spanning tree. The graph representing
> > > > > all the paths from one vertex to all the others must be a spanning
> tree
> > > > > - it must include all vertices. There will also be no cycles as a
> cycle
> > > > > would define more than one path from the selected vertex to at least
> > > > > one other vertex. For a graph, G=(V,E) where V is a set of vertices
> and
> > > > > E is a set of edges.
> > > > > Dijkstra's algorithm keeps two sets of vertices: S (the set of
> vertices
> > > > > whose shortest paths from the source have already been determined)
> and
> > > > > V-S (the remaining vertices). The other data structures needed are:
> d
> > > > > (array of best estimates of shortest path to each vertex) & pi (an
> > > > > array of predecessors for each vertex)
> > > > > The basic mode of operation is:
> > > > > 1. Initialise d and pi,
> > > > > 2. Set S to empty,
> > > > > 3. While there are still vertices in V-S,
> > > > > i. Sort the vertices in V-S according to the current best
> estimate of
> > > > > their distance from source,
> > > > > ii. Add u, the closest vertex in V-S, to S,
> > > > > iii. Relax all the vertices still in V-S connected to u
> > > > > Dijkstra Algorithm:
> > > > > DIJKSTRA(Graph G,Node s)
> > > > > initialize_single_source(G,s)
> > > > > S:={ 0 } /* Make S empty */
> > > > > Q:=Vertices(G) /* Put the vertices in a PQ */
> > > > > while not Empty(Q)
> > > > > u:=ExtractMin(Q);
> > > > > AddNode(S,u); /* Add u to S */
> > > > > for each vertex v which is Adjacent with u
> > > > > relax(u,v,w)
> > > > >
> > > > >
> > > > > >
> > > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > >
> >
> >
> >
> >
> >
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
