Why doesn't pgRouting return the best path?

Question

Let the next portion of a graph:

When I use the function shortest_path between the points A and B, I got the blue path. Why does this happen?

Answer 1

That's how shortest_path (Dijkstra's algorithm) behaves in pgRouting. If there are two edges with same source and target, random one (to be precise: first one, that comes out from database) is used. I don't know any fix for that, but there are some workarounds.

If possible, you should split one of those edges into two. I haven't tested it, but it should fix that behaviour.

Other solution for case, when you can't modify your dataset. Add field 'shorter_alternative' to your table. Sample query, modify it to your needs. I hope it explains idea:

UPDATE roads t1
SET shorter_alternative = t2.id
FROM roads t2
WHERE 
((t2.source = t1.source AND t2.target = t1.target) OR
(t2.source = t1.target AND t2.target = t1.source)) AND
(t2.length < t1.length)

Now, edge '0.098' will contain id of edge '0.011'. All other edges will have null in shorter_alternative field. After you have made shortest_path query, check returned dataset - if any rows has shorter_alternative field set, change it.

Answer 2

I've actually created a patch for pgRouting, that fixes the problem: https://github.com/pgRouting/pgrouting/issues/78

Answer 3

The problem already has been described in the previous answer. It's a problem of "vertex-based" shortest path algorithms, that only care about source and target.

There is a ticket in the issue tracker and a possible solution to change the algorithm implementation: https://github.com/pgRouting/pgrouting/issues/34 (Would be nice if someone could try this out and send a pull request ;-)

Another possibility is to split "parallel road links" as mentioned before. Or you could use Shooting Star algorithm, which routes from edge to edge so it "knows" about both road links.

Or you can try to order the road network by cost and then select only distinct combinations of source and target:

SELECT * FROM shortest_path(
  'SELECT DISTINCT ON (source, target)
      gid as id,
      source::integer,
      target::integer,
      cost::double precision
    FROM ways ORDER BY source, target, cost',
  true,false
);

This assumes that you search for the least expensive route. Otherwise you need to ORDER BY ... DESC.

You need to try out if this affects performance.