Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
In the explanation, I made a mistake, is red blue not red, sorry! – José Alejandro Jan 4 '13 at 15:44
up vote 7 down vote accepted

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 =
FROM roads t2
((t2.source = t1.source AND = OR
(t2.source = AND = 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.

share|improve this answer
Thanks for pointing out this awful trap! – underdark Jan 3 '13 at 21:45

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: (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,
      cost::double precision
    FROM ways ORDER BY source, target, cost',

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.

share|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

I've actually created a patch for pgRouting, that fixes the problem:

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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