5

I think I found an interesting bug in pgrouting. When I use the Dijkstra algorithm (no matter if I use the shortest_path() or dijkstra_sp_delta_directed() method) to calculate the directed shortest paths between two particular vertexes (id 72846 and id 85556), it only delivers the correct result for one direction.

I experimented a little bit and then I found out that there are two arcs in the roads_po table with opposite direction which connect two vertexes that are part of both calculated shortest paths (gid 700 and gid 169244).

When I calculate the shortest path from vertex 72846 to vertex 85556, everything works fine as can be seen here:

correct_result:

enter image description here

But when I calculate the shortest path from vertex 85556 to vertex 72846 (the opposite direction), the wrong arc with gid 169244 instead of the correct arc with gid 700 is chosen resulting in a violation of the one-way direction.

wrong_result:

enter image description here

It seems that pgrouting calculates both paths correct, but it has a problem that two vertexes along the paths are connected by two arcs, and chooses the wrong arc for output for one of the paths.

Did someone else had such problems with pgrouting?

1 Answer 1

1

directions in opposite direction may read different edges of the same segment. depends on how you data encodes segment edges with one ways and how it is read out by the application. Without logic rules handling edges of same segments with oneways as models existing within the database I would anticipate uneven results. You segment would have at least four directions of travel and if blocking was not handled correctly for all cases, or edges routing was not considered you might have a similar problem.

1
  • The one-ways are encoded using the reverse_cost column in the roads_po table. Arcs that correspond to a one-way have a value of 1.0E6 while non-one-ways have the same value in the reverse_cost column which they also have in the length column. Feb 1, 2013 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.