On May 13, 3:19 pm, Jaime Fernandez del Rio <jaime.f...@gmail.com> wrote: > Dijkstra's algorithm computes shortest paths between a node and _ALL_ > other nodes in the graph. It is usually stopped once computing the > shortest path to the target node is done, but that's simply for > efficiency, not a limitation of the algorithm. So you should be able > to tweak the code you are using so that it provides you with all you > are looking for. I'd be surprised if graphine (which, by the way, > looks great, CTO) or any other graph package didn't implement it, so > switching to that may be the most efficient thing to do. > > On the other hand, if you want to post your code and links to the > Dijkstra code you are using it may be possible to help you with the > tweaking... > > Jaime > > > > On Wed, May 13, 2009 at 8:31 AM, godshorse <chinthak...@gmail.com> wrote: > > On May 13, 11:54 am, CTO <debat...@gmail.com> wrote: > >> On May 13, 12:10 am, godshorse <chinthak...@gmail.com> wrote: > > >> > Hello, > > >> > I want to find out the shortest path tree from a root to several nodes > >> > in a graph data structure. I found a Dijkstra code from internet that > >> > finds shortest path between only two nodes. How can i extend it to a > >> > tree?. And what is the best way to represent a tree in Python?. > > >> > Thank you, > > >> Well, I'm biased, but I like <URL:http://graphine.org>. > >> As an example, to build a five node tree: > > >> >>> from graph.base import Graph > >> >>> g = Graph() > >> >>> for i in range(5): > > >> ... g.add_node(i) > >> ... > > >> >>> g.add_edge(0, 1) > >> >>> g.add_edge(0, 2) > >> >>> g.add_edge(1, 3) > >> >>> g.add_edge(1, 4) > > >> And to find the shortest path between, say, node 0 and node 4: > > >> >>> start = g[0] > >> >>> end = g[4] > >> >>> distance, edges = g.get_shortest_paths(start)[end] > >> >>> distance > >> 2 > >> >>> edges > > >> [Edge(name=(0,1)), Edge(name=(1,4))] > > >> Let me know what you think if you decide to use it- I'm looking for > >> feedback. > > >> Geremy Condra > > > Thanks very much for your reply Geremy. That site was interesting. > > > Actually the Graph building part is already completed now. I used a > > dictionary for that and it works fine. for Dijkstra shortest path > > problem your suggestion can be used. > > > But let me clear the my problem again. I have a graph. and I want to > > find 'shortest path tree' from a root node to several nodes. as a > > example if we have a graph of 5 nodes from 1 to 5, I need to build the > > shortest path tree from node 1 to nodes 2,3,5. So my question is > > instead of keeping separate lists for each destination node's shortest > > path. How can I represent and store them in a tree structure using > > python. Then I can easily find out what are the common nodes in the > > path to each destination. > > > Thanks once again. > > -- > >http://mail.python.org/mailman/listinfo/python-list > > -- > (\__/) > ( O.o) > ( > <) Este es Conejo. Copia a Conejo en tu firma y ayúdale en sus > planes de dominación mundial.
Hello Jaime, Thanks for the reply. This is the link to the code that I am using. http://code.activestate.com/recipes/119466/ What I do in my code is just looping through the destination nodes and find the shortest path to each node. Thanks -- http://mail.python.org/mailman/listinfo/python-list
