9

Let the next portion of a graph:

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

  • In the explanation, I made a mistake, is red blue not red, sorry! – José Alejandro Jan 4 '13 at 15:44
7

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.

|improve this answer|||||
2

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.

|improve this answer|||||
  • Yesterday I build the trsp function and look like not have this issue. Anyway, thanks for the explanation!!!. – José Alejandro Jan 4 '13 at 15:40
2

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

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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