Hi Marcus, I believe that if I don't have a description than nobody has it. And unfortunately I don't have any :( I can give you some hints and ideas, but I never had time to make any kind of scientific papers.
Shooting* is edge-based, so it goes from edge to edge while A* and Dijkstra go vrom vertex to vertex. Thus you need a data structure which keeps all adjacent edges for every edge of your graph. It can be also done by making a line graph (http://en.wikipedia.org/wiki/Line_graph) out your original road network. And then you can assign an edge-to-edge passage cost (as a special attribute of your adjacent edges structure or as a cost of the line graph) which actually represents any kind of limitations or penalties for going from one edge to another - such as turn restrictions in a case of turns or any other kind of restrictions like traffic lights. Having this you can use A* or any other shortest path algorithm using edges as vertices. So, that's an idea behind the Shooting*. I am ready to help you with your implementation, so please contact me if you need any help. Anton. On Mon, Mar 23, 2009 at 8:38 PM, <marcus.wolsc...@googlemail.com> wrote: > > > Hello, > > does anyone have a description of the ShootingStar routing-algorithm? > It is implemented in pgRouting and can do tun-restrictions quite nicely > but that is all I could figure out. > I would like to implement it myself and see how it performs. > > Marcus > > _______________________________________________ > Routing mailing list > Routing@openstreetmap.org > http://lists.openstreetmap.org/listinfo/routing > _______________________________________________ Routing mailing list Routing@openstreetmap.org http://lists.openstreetmap.org/listinfo/routing
