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