[GRASS5] Re: Shortest path

[Kjell-Olav Bjerknes]

At 13:40 05.10.2000 +0200, you wrote:
>Ok for shortcuts, but what if my window is huge too?
>Tell me if I'm wrong: when we get to calculating the path we need select 
>groups of arcs sharing
>from_node, and link that node with relative to_nodes.
>This means O(#from_node). What if I have to perform 100.000 select?

I looked through my Java-code, and the Dijkstra algorithm loaded all the 
nodes in the network in an array and the cost from the startnode to each 
other node was recorded as the algorithm worked through the network. Since 
we only had a small network this worked fine. I dont know how fast Grass 
could work on arrays containing 100 000's nodes, maybe these arrays must be 
saved in RDBMS? Beside of this cost array, we also used two other arrays. 
One keeping the shortest path for a node to the start node. The last array 
marked the nodes "visited" as the alogrithm worked its way to the goal! The 
algortihm stoped when the stop node was marked visited!

Our arrays were build every time the application was run. This doesnt have 
to be the case. The arrays/tables in RDBMS needs only to be created when 
the network has been updated.! Constructing a command that does this after 
updating the network should be an easy task and would save some time!


Kjell-Olav


---------------------------------------- 
If you want to unsubscribe from GRASS Development Team mailing list write to:
minordomo at geog.uni-hannover.de with
subject 'unsubscribe grass5'