[GRASS5] Re: Shortest path

[Roberto Micarelli]

Kjell-Olav Bjerknes wrote:
> 
> 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

Ok. Now I'm writing my version of the graph library, I need it apart from Grass
but hope it will be useful in there too. Don't apologize me for not to listen to
your suggestions, I'm doing that. But I also must start to stay into planned time.
I'm using an 'offset method' to address nodes both into the memory array and/or
in the database file. So when I block-read the graph in memory I have ready to
use memory offsets.
Dijkstra has to exhaust nodes before giving up with the best path. If you stop
it the first time you reach the target, nobody can tell you that it's really the
best way. I'm thinking to some smart short-cuts expecially oriented to vehicle
navigation ...
Didn't you use a min-heap for costs?
I'm going to send to people interested in my work a copy, as soon as it is in
a suitable aspect. It is C code developed/compiled under Linux. I'll
need to test it for porting on other OS. When it will be enought stable I'll wrap
it to Grass and propose for adoption to this community.

Is your Java application available for reading?

Roberto

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