dijkstra (#16) - Dijkstra sometimes chooses wrong edges (#350) - Message List

Dijkstra sometimes chooses wrong edges

Hi there,

I've got a strange problem. Click this link to run a route on Ride the City:  http://www.ridethecity.com/toronto?rid=568835

It should route you (incorrectly) down a street called Axsmith Cres. It should be fairly obvious that this is not the shortest route and it would be shorter to continue on Van Horne Ave.

I've confirmed that the cost of Van Horne Ave is MUCH lower than the cost of Axsmith Cres. And I've confirmed that there is nothing else wrong with the Van Horne Ave edge. For example, if I delete the Axsmith Cres edge, then the route DOES use Van Horne Ave as expected.

Both edges have the same source and target. Aside from that, I don't see anything unusual. Could there be another factor? Or do you have any troubleshooting suggestions?

Here is my SQL: select * from dijkstra_sp_directed('toronto_active'::character varying, 11068, 29486, true, true)

Can I provide anything else that could help troubleshoot the problem? e.g. the output from the SQL above? Relevant database records?

Thanks, Jordan

ja3n
04/13/10 05:16:57 (7 months ago)
Tree View Flat View (newer first) Flat View (older first)
  • Message #1458

    Hi Jordan,

    This is the exactly the "bug" we had once when preparing the FOSS4G workshop for Victoria in 2007. We used the freely available road network data for Canada, and as far as I know, this data has been imported into OSM then.

    The problem is that there are two road links with same start and end point. Dijkstra and A* route from node to node, so they actually don't care about edge cost. And the topology function takes either cost for one or the other road. So sometimes it's correct and sometimes not. You can't control this. There are a lot of this kind of roads like in your example.

    You can do two things: either use Shooting* algorithm or split all "parallel links (search for all road links with same start and end).

    daniel
    04/13/10 07:02:48 (7 months ago)
Tree View Flat View (newer first) Flat View (older first)