[pgrouting-users] Bug in pgr_bdDijkstra?

[Thomas Höhne]

Hello PG-Routing - users,

I hope, this is the right address for my mail...

We are using pg-routing since some years and we are very impressed by the functionality and the speed.

Today we tried first time pg_routing Version 2.0 (2.0.0,pgrouting-2.0.0,0,d6ed2cb,master,1.46.1) on PostgreSQL 9.2.4, compiled by Visual C++ build 1600, 64-bit with POSTGIS="2.1.1 r12113" GEOS="3.4.2-CAPI-1.8.2 r0" PROJ="Rel. 4.8.0, 6 March 2012" GDAL="GDAL 1.10.0, released 2013/04/24" LIBXML="2.7.8" LIBJSON="UNKNOWN" TOPOLOGY (topology procs from "2.0.3 r11132" need upgrade) RASTER.

When updating our code we replaced shortest_path through pgr_bdDijkstra.
And then we saw that the result of this algorithm seems to be false. But only when not using reverse costs.

Here a simple test case, where we can reproduce the behaviour:
There are three Points. Costs from 1 to 2 and 2 to 3 are 1. Costs from 3 to 1 are 1.5. Reverse costs are equal.
When we search the shortest path from 3 to 1, the algorithm should use the direct connection. But it does not:

select sp.id1::int4 as vertex_id, sp.id2::int4 as edge_id, sp.cost::float8
        from pgr_bdDijkstra('
select 1::int4 as id, 1::int4 as source, 2::int4 as target, 1::float8 as cost, 1::float8 as reverse_cost
union all
select 2::int4 as id, 2::int4 as source, 3::int4 as target, 1::float8 as cost, 1::float8 as reverse_cost
union all
select 3::int4 as id, 3::int4 as source, 1::int4 as target, 1.5::float8 as cost, 1.5::float8 as reverse_cost',
3, 1, false, false) sp

result (vertex_id, edge_id, cost):
3;2;0
2;1;0
1;-1;0
-> wrong edges and even wrong costs

when we use as last option "true" (has_rcost) the result is ok:
3;3;1.5
1;-1;0
-> correct result

when we walk from 1 to 3 without reverse costs:
1;3;0
3;-1;0
-> right edges but still wrong costs

After trying a while we saw, that there is also a pgr_dijkstra - routine in pg-routing 2.0, which seems to make the same as earlier the shortest_path.
We take this function now and that seems to work perfect (same sql as above but with pgr_dijkstra):
3;3;1.5
1;-1;0
-> correct result

We are not sure, whether we used the pgr_bdDijkstra correct. But we think we did and we think the result of this function is not correct.
We did not find this problem described somewhere, that's why we wanted to inform you.

It would be nice, if you let us know, whether this is really a bug or if we are doing something wrong.

Thanks and Regards

Thomas Höhne

IDU Ingenieurgesellschaft für Datenverarbeitung und Umweltschutz mbH
Thomas Höhne

Goethestraße 31
02763 Zittau
Germany

Tel     03583 5409 499 / 5409 497
Fax     03583 5409 / 498
Internet  www.idu.de<http://www.idu.de>



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20131210/7d97c3c1/attachment.html>