pgRouting

Ticket #110 (closed bug report: invalid)

Opened 7 months ago

Last modified 6 months ago

Dijkstra fails on parrallel edges

Reported by: erik_heinz Assigned to: somebody
Priority: major Milestone:
Component: Dijkstra Version: 1.01
Keywords: Cc:

Description

It seems to me that shortest_path() does not find the shortest path in the case where redundant edges having the same source and target nodes are involved. To illustrate the problem I created a table of only two parallel edges: 

gisdata=# select * from edges;  
 id | source | target | length
----+--------+--------+--------
  1 |      1 |      2 |    5.5
  2 |      1 |      2 |    4.4
(2 rows)

When travelling from node 1 to node 2 shortest_path() should select edge 2 because of the lower cost. It selects edge 1 instead, probably since edge 1 is returned by Postgresql first: 

gisdata=# select * from shortest_path('SELECT id, source, target, length AS cost FROM edges', 1, 2, false, false);
 vertex_id | edge_id | cost
-----------+---------+------
         1 |       1 |  5.5
         2 |      -1 |    0
(2 rows)

This seems wrong to me or do I miss something?

Thank you, Erik

Change History

05/09/08 11:00:02 changed by anton

  • status changed from new to closed.
  • resolution set to invalid.

Hi Erik,

There is no bug here. You know, Dijkstra and A* are vertex based algorithms. It means that they know nothing about edges and they only care about cost of going from a to b. In case of parallel edges (your case for example) when the algorithms reaches vertex 1 it searches for adjacent vertexes and it finds only one vertex 2. It doesn't care about which way is better and takes the first way (edge) it can find. Sometimes it is the shorter edge and sometimes not.

There are two ways to resolve this - to split parallel edges or to use Shooting* algorithm (which is edge based and cares about edges).

See also #15