If you run Dijkstra without a third argument, i.e. without an end
node, the it will compute the shortest paths from your start node to
all nodes in the tree. So by doing something like:
start_node = 1
end_nodes = [2,3,5]
D, P = Dijkstra(G, start_node)
You will then have in D a dictionary with distances to all nodes, and
in P a dictionary of preceding nodes along the shortest path for each
node. You could tweak the Dijkstra function so that it stops when the
minimum distances to all elements of end_nodes have been calculated,
without having to solve for the whole graph...
Apart from that, how you want to store the shortest path information
is up to you, but if you stick to the "graph as a dictionary of
dictionaries" you can construct the subgraph that contains only the
nodes in the shortest paths between the start and the end nodes with
code like this one:
shortest_tree = {}
current_layer = end_nodes
while current_layer != [start_node] :
new_layer = set()
for node in current_layer :
new_node = P[node]
if new_node in shortest_tree :
if node not in shortest_tree[new_node] :
shortest_tree[new_node][node] = G[new_node][node]
else :
shodtest_tree[new_node] = {}
shortest_tree[new_node][node] = G[new_node][node]
new_layer.add(new_node)
current_layer = [j for j in new_layer]
I haven't tested the code, and there may be more efficient ways of
achieving the same, though...
Jaime
On Wed, May 13, 2009 at 10:49 AM, godshorse <chinthak...@gmail.com> wrote:
> 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
>
--
(\__/)
( O.o)
( > <) Este es Conejo. Copia a Conejo en tu firma y ayúdale en sus
planes de dominación mundial.
--
http://mail.python.org/mailman/listinfo/python-list
