[pgrouting-users] Bug in pgr_bdDijkstra?

[Stephen Woodbridge]

Hi Thomas,

Thank you for the report and a clear way to reproduce the issue. I just 
opened this bug report for this issue:

https://github.com/pgRouting/pgrouting/issues/227

Thanks,
   -Steve

On 12/10/2013 3:54 PM, Thomas Höhne wrote:
> 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>
>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>