[algogeeks] Re: find all paths from one node to another node

Tue, 09 May 2006 07:02:55 -0700

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
-~----------~----~----~----~------~----~------~--~---

Reply via email to