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