Representing a Tree in Python

[Jaime Fernandez del Rio]

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 <chinthakawk at gmail.com> wrote:
> On May 13, 11:54 am, CTO <debat... at gmail.com> wrote:
>> On May 13, 12:10 am, godshorse <chinthak... at 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.