Routers will all do pre-processing on the network, to a) eliminate edges
(ways) that are irrelevant for routing, b) combine consecutive segments
wherever possible and c) precalculate the cost (usually journey time) of
each edge.
Dijkstra has been improved upon by e.g. the A* algorithm:
https://en.wikipedia.org/wiki/A*_search_algorithm
If a way NEEDS to be split, because different segments have different
tagging and/or relation memberships, then that's fine because there is
no alternative. But to split ways at every junction under the
misapprehension that this helps a "router" or other data consumer, is
just wrong.
On 2018-01-13 15:58, David Woolley wrote:
> On 13/01/18 14:42, Dave F wrote:
>
>> When a router traversing a way encounters a node it does a check to see if
>> other ways are connected, If they are, it analyses the tags on those ways &
>> decides if needs to go down one of them or continue to the next node.
>> There's no requirement to split.
>
> Whilst I don't know the specific algorithms used by current routers, the
> standard algorithms for the shortest path through a network
> <https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm> requires a list of
> nodes and edges, and creates the full tree of possible routes out from that
> endpoint, assigning costs to reach each node.
>
> Whilst it might be possible to deduce edges and assign costs to the edges on
> the fly, that is likely to result in more processing, and mean one has to
> customise the standard algorithm.
>
> On the other hand, one could argue that this is almost a case of tagging for
> the renderer. I'd certainly say it was a misuse of the map database.
>
> (I suspect routers use some heuristics to avoid searching too many edges.)
>
> _______________________________________________
> Talk-GB mailing list
> Talk-GB@openstreetmap.org
> https://lists.openstreetmap.org/listinfo/talk-gb
_______________________________________________
Talk-GB mailing list
Talk-GB@openstreetmap.org
https://lists.openstreetmap.org/listinfo/talk-gb
