Re: Representing a Tree in Python

2009-05-23 Thread Albert van der Horst
In article <43289c33-04b9-4cbc-9823-d8a4ee86d...@y33g2000prg.googlegroups.com>, godshorse wrote: >On May 13, 11:54=A0am, CTO wrote: >> On May 13, 12:10=A0am, godshorse wrote: >> >> > Hello, >> >> > I want to find out the shortest path tree from a root to several nodes >> > in a graph data struc

Re: Representing a Tree in Python

2009-05-15 Thread Jaime Fernandez del Rio
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 di

Re: Representing a Tree in Python

2009-05-14 Thread Benjamin Edwards
On May 13, 8:27 pm, CTO wrote: > On May 13, 8:19 am, bearophileh...@lycos.com wrote: > > > godshorse, you may use the "shortestPaths" method of this graph class > > of mine:http://sourceforge.net/projects/pynetwork/ > > > (It uses the same Dijkstra code by Eppstein). > > (Once you have all distanc

Re: Representing a Tree in Python

2009-05-13 Thread CTO
On May 13, 8:19 am, bearophileh...@lycos.com wrote: > godshorse, you may use the "shortestPaths" method of this graph class > of mine:http://sourceforge.net/projects/pynetwork/ > > (It uses the same Dijkstra code by Eppstein). > (Once you have all distances from a node to the other ones, it's not >

Re: Representing a Tree in Python

2009-05-13 Thread Piet van Oostrum
> godshorse (g) wrote: >g> Hello, >g> I want to find out the shortest path tree from a root to several nodes >g> in a graph data structure. I found a Dijkstra code from internet that >g> finds shortest path between only two nodes. How can i extend it to a >g> tree?. And what is the best way t

Re: Representing a Tree in Python

2009-05-13 Thread bearophileHUGS
godshorse, you may use the "shortestPaths" method of this graph class of mine: http://sourceforge.net/projects/pynetwork/ (It uses the same Dijkstra code by Eppstein). (Once you have all distances from a node to the other ones, it's not too much difficult to find the tree you talk about). Also se

Re: Representing a Tree in Python

2009-05-13 Thread godshorse
On May 13, 3:19 pm, Jaime Fernandez del Rio 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 al

Re: Representing a Tree in Python

2009-05-13 Thread 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 usi

Re: Representing a Tree in Python

2009-05-13 Thread CTO
> 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

Re: Representing a Tree in Python

2009-05-12 Thread godshorse
On May 13, 11:54 am, CTO wrote: > On May 13, 12:10 am, godshorse 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 ext

Re: Representing a Tree in Python

2009-05-12 Thread CTO
On May 13, 12:10 am, godshorse 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