bug : Bellman-Ford/DAG ignore negative costs despite documented support — base_graph filtering

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

Maintainers usually reply within 3 days

Nobody has claimed this yet.

Assessment

Difficulty
3/5
Estimated time
1-2 days
Newbie friendliness
65/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
cpp, postgresql
Domain
backend, databases

Research direction

The issue is in src/dijkstra/shortestPath_driver.cpp and include/cpp_common/base_graph.hpp. Start by examining the graph_add_edge function (lines 732-761) that filters negative costs. Look at the driver's insert_edges call (line 240, 268) and the Which enum in include/c_common/enums.h to identify the algorithm types. The fix requires adding a new insertion function that allows negatives and routing Bellman-Ford, EdwardMoore, and DAGSP through it. Run the provided SQL queries to verify the bug and test the fix.

Written by the indexing model from the issue text.

Description

bug Looks AI

Problem

The documented negative-cost support for pgr_bellmanFord, pgr_edwardMoore, and pgr_dagShortestPath does not actually work.

doc/bellman_ford/pgr_bellmanFord.rst:42,47 states some edge weights may be negative and the process is valid for edges with both positive and negative weights. The algorithm wrappers (include/bellman_ford/bellman_ford.hpp:132 boost::bellman_ford_shortest_paths, include/bellman_ford/edwardMoore.hpp:180 queue relaxation, and include/dagShortestPath/dagShortestPath.hpp:131 boost::dag_shortest_paths) all handle negatives.

However, every call goes through src/dijkstra/shortestPath_driver.cpp:240,268 (digraph.insert_edges(edges)) → include/cpp_common/base_graph.hpp:732-761 (graph_add_edge), where edges are guarded with if(cost>=0) and if(reverse>=0). Negatives are dropped before the algorithms ever receive them. This matches the Dijkstra contract (doc/src/pgRouting-concepts.rst:85,108 and doc/dijkstra/dijkstra-family.rst:57-59), but directly contradicts the Bellman and DAG contracts. The sibling helper base_graph.hpp:815-850 (graph_add_neg_edge) converts negative costs via (-0.5) * cost with a TODO at line 816, so it cannot be reused as-is.

To Reproduce

-- Bellman: negative middle edge should be used
SELECT * FROM pgr_bellmanFord(
  'SELECT * FROM (VALUES (1,1,2,5),(2,2,3,-4),(3,1,3,10)) AS t(id,source,target,cost)',
  1, 3, true);
-- Expected Bellman: path 1->2->3, agg_cost = 1
-- Actual today: path 1->3, agg_cost = 10 (the -4 edge was filtered out)

-- Bellman: negative reverse_cost on undirected graph
SELECT * FROM pgr_bellmanFord(
  'SELECT * FROM (VALUES (1,1,2,5,2),(2,2,3,10,-3)) AS t(id,source,target,cost,reverse_cost)',
  1, 3, false);
-- Expected: reverse edge with negative cost is traversed; Actual today: ignored

-- DAG: negative on an acyclic graph should be used
SELECT * FROM pgr_dagShortestPath(
  'SELECT * FROM (VALUES (1,1,2,-2),(2,2,3,1),(3,1,3,5)) AS t(id,source,target,cost)',
  1, 3);
-- Expected: path 1->2->3, agg_cost = -1
-- Actual today: path 1->3, agg_cost = 5

-- Dijkstra on identical data should preserve current behavior (negative = edge does not exist)
SELECT * FROM pgr_dijkstra(
  'SELECT * FROM (VALUES (1,1,2,5),(2,2,3,-4),(3,1,3,10)) AS t(id,source,target,cost)',
  1, 3, true);
-- Expected & Actual: path 1->3, agg_cost = 10 (filtering preserved)

Expectation

  • pgr_bellmanFord/pgr_edwardMoore (directed and undirected) and pgr_dagShortestPath (directed) include both negative cost and reverse_cost values in the graph so underlying solvers (boost::bellman_ford_shortest_paths, edwardMoore, dag_shortest_paths) can route through them.
  • pgr_dijkstra, pgr_bdDijkstra, pgr_aStar, and pgr_bdAstar preserve their current filter (cost < 0 implies the edge does not exist).
  • No changes to public SQL signatures or empty-SQL query checks (ERROR: Empty edges SQL at shortestPath_driver.cpp:145-148).

Sample Data

The inline VALUES queries above reproduce the issue directly. Alternatively, using the standard sample dataset:

INSERT INTO edges(id, source, target, cost) VALUES (-1, 1, 2, -4);

Platform/versions

SELECT version();            -- PostgreSQL 17.x (affects 13-18, logic is in the C++ graph layer)
SELECT postgis_full_version();
SELECT pgr_version();        -- 4.1.0-dev, develop @ 350b1e533
  • OS: Ubuntu 24.04 (platform-independent C++ graph logic)

Proposed approach
Minimal two-file fix without changing SQL signatures:

  1. Add insert_edges_allow_negative / graph_add_edge_allow_negative to include/cpp_common/base_graph.hpp (a non-filtering variant that stores cost and reverse_cost as-is, unlike graph_add_edge at lines 732–761).
  2. Route BELLMANFORD, EDWARDMOORE, and DAGSP through this new insertion path in src/dijkstra/shortestPath_driver.cpp:239-292 by matching on Which (include/c_common/enums.h:34-36), ensuring DAG applies only to directed calls.
  3. Keep Dijkstra/BDD/A*/BFS/WITHPOINTS on the existing filtered path.
  4. Add pgTAP regression tests covering negative cost and reverse_cost for Bellman-Ford and DAG.

Happy to follow ur direction ! :)

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.