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 algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
