bug: Undirected graph with cost != reverse_cost: aStar, bdAstar and bdDijkstra functions return every node and edge twice

Open
  • Is something wrong?
#3,180 4 comments 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 3 days

@AdityaRanaX is already working on this.

Since Nov 12, 2026.

  • #3191 by @AdityaRanaX — open

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
30/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
c, cpp, postgresql
Domain
backend

Research direction

Start with the Path(graph, original, only_cost) constructor in include/cpp_common/path.hpp, around lines 196-202, which pushes a row for every out-edge whose id matches instead of one per step. Reproduce with the edges_undirected_asym table from the issue: pgr_dijkstra should return agg_cost 10 and pgr_bdDijkstra should match it. Done means the bidirectional and A* families return the same rows as pgr_dijkstra for asymmetric undirected graphs, with the existing tests still passing.

Written by the indexing model from the issue text.

Description

bug Looks AI valid

Summary

With directed => false, when an edge has both cost and reverse_cost non-negative and different, the aStar, bdAstar and bdDijkstra families return a path in which every node and every edge appears twice, and agg_cost adds up both weights. pgr_dijkstra, pgr_KSP and pgr_dijkstraVia return the expected result for the same input.

Reproduce

CREATE TEMP TABLE edges_undirected_asym AS
SELECT * FROM (VALUES
(1::BIGINT, 1::BIGINT, 2::BIGINT, 7::FLOAT, 2::FLOAT),
(2, 2, 3, 7, 2),
(3, 3, 4, 7, 2),
(4, 4, 5, 7, 2),
(5, 5, 6, 7, 2)
) AS t(id, source, target, cost, reverse_cost);

-- expected result
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges_undirected_asym',
1, 6, false);

-- wrong result
SELECT * FROM pgr_bdDijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges_undirected_asym',
1, 6, false);

Expected

6 rows and a final agg_cost of 10, using each edge once at cost 2.

doc/src/pgRouting-concepts.rst describes an undirected edge with two costs as two parallel edges between the same vertices, both with the same id, one weighing cost and one weighing reverse_cost. Using the cheaper one at every step gives 5 * 2 = 10. I also checked this without any pgRouting algorithm, by expanding every row into those arcs and enumerating the simple paths from 1 to 6: the minimum is 10.

Actual

pgr_dijkstra: 6 rows, agg_cost 10.

pgr_bdDijkstra: 11 rows, agg_cost 45. Every node and every edge appears twice, once with cost 7 and once with cost 2:

seq | node | edge | cost | agg_cost
1 | 1 | 1 | 7 | 0
2 | 1 | 1 | 2 | 7
3 | 2 | 2 | 7 | 9
4 | 2 | 2 | 2 | 16
...
11 | 6 | -1 | 0 | 45

45 = 5 * (7 + 2). It is not the cost of any walk in that graph.

Affected functions (tested with this graph and a second 4-edge graph)

Wrong: pgr_aStar, pgr_aStarCost, pgr_aStarCostMatrix, pgr_bdAstar, pgr_bdAstarCost, pgr_bdAstarCostMatrix, pgr_bdDijkstra, pgr_bdDijkstraCost, pgr_bdDijkstraCostMatrix.

Expected result: pgr_dijkstra, pgr_KSP (k = 1), pgr_dijkstraVia.

Directed graphs, and undirected graphs with cost = reverse_cost, give the expected result in all twelve functions.

Also reproduced on pgRouting 4.0.0 (pgr_dijkstra 10, pgr_bdDijkstra 45), so it is not recent. The bidirectional fix proposed in #3174 does not change this behaviour.

Where it seems to come from

From reading the code, not from instrumenting it:

  • include/cpp_common/base_graph.hpp (graph_add_edge, around lines 774-781) stores such an undirected edge as two internal edges with the same id, which matches the documentation.
  • include/cpp_common/path.hpp (the Path(graph, original, only_cost) constructor, around lines 196-202) looks up each step by id and pushes a row for every out-edge whose id matches, without a break. Both parallel edges match, so both are kept, and agg_cost is recomputed from all of them.
  • That constructor is only called from include/astar/astar.hpp and include/cpp_common/bidirectional.hpp, which is the list of affected functions.
  • pgr_dijkstra builds its result through get_edge_id(), which returns exactly one edge and uses the cost to choose, so it is not affected.

Why the tests do not catch it

The sample edges table only has rows with (1, 1), (-1, 1) or (1, -1) as cost and reverse_cost, so no row has two different non-negative weights. The compare_dijkstra tests start with

UPDATE edges SET cost = sign(cost) + 0.001 * id * id, reverse_cost = sign(reverse_cost) + 0.001 * id * id;

which keeps cost and reverse_cost equal.

Possible direction (not tested)

In the Path constructor, push one row per step instead of one per matching edge, choosing the one whose cost matches the step's recorded cost or the cheapest, as get_edge_id() does. I have not tried this.

Dominant language
C++
Stars
1.4k
Forks
397
Avg merge
2d 16h
Merged PRs (30d)
8

Getting set up

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from pgRouting/pgrouting

All issues in pgRouting/pgrouting

Similar issues

More C++ issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.