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
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
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?.
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_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.
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.
--
(\__/)
(
)
( > <) 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
