Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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
add comment

3 Answers 3

up vote 6 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 = 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.

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

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

share|improve this answer
add comment

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.

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
add comment

Your Answer

 
discard

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.