Bug in shortest_path and two edges between same nodes

[tokrsen]

If the network contains two (or more) edges between the same nodes shortest_path returns everytime the first one without cost accounting.

  ________10________ 
[1]                 [2]
 |                   |
 |________20_________| 

Here is the test case with wrong result.

SELECT * FROM shortest_path('
  SELECT unnest(array[1,2]) as id, 
    unnest(array[10,10]) as source,
    unnest(array[20,20]) as target,
    unnest(array[2,1])::float8 as cost
  ',10,20,false,false);

Workaround is in using "ORDER BY cost" but it is not a good solution.

[dkastl]

This is not really a bug but caused by how Dijkstra algorithm works: Dijkstra and also A-Star route from node to node, which is the only information they have about the network. Order by cost is actually a nice workaround I haven't thought about yet, because you're right: it just takes the first suitable node pair. To check for duplicate node pairs would probably be bad for performance. Other possibilities would be to split one of those road links into two when preparing the network topology. Or you use Shooting Star algorithm, which routes from edge to edge and doesn't know this problem.

[tokrsen]

Thanks for the answer. I understand. It is a real question if "order by" is better then duplicates checking in Dijkstra algorithm from the performance side of view.

But if ORDER BY is needed for the right result it should be described in documentation.

[dkastl]

It has been mentioned a couple of times already as "parallel links": http://workshop.pgrouting.org/chapters/shortest_path.html#shooting-star ftp://ftp.remotesensing.org/pgrouting/forum/pgrouting.postlbs.org/discussion/topic/350.html http://download.osgeo.org/pgrouting/forum/pgrouting.postlbs.org/ticket/110.html

Well, it would be possible to add some howto page for example to the documentation. "order by" is a nice way to solve this. Or adding a note to the documentation would be also fine.

You're welcome to add some explanation to the website, which is also available as Git repository: https://github.com/pgRouting/website/tree/master/docs

[woodbri]

According to Jeremiah Willcock of the BGL list: "That one is a relatively easy fix -- use edge_predecessor_recorder (which is undocumented, but works like predecessor_recorder) as a visitor for Dijkstra and A*; that will give you edge IDs back directly for each path."

So this should get looked into when we have a chance for someone with Boost/C++ experience to look at adding this.

[woodbri]

Obviously we could check every edge we add to see if it was previously added and make sure it has smallest cost. We would also need to check the reverse costs, but I expect that doing all this checking might take too much time. We could also look at sorting the edges internally with something like qsort and then checking as we insert them which would probably be faster. Another option might be to modify the SQL query for the edges to add an ORDER BY doing something like:

select * from ( ) order by cost asc;