Hacktoberfest 2026：维护者为十月标记出来的 issue，仍然开放、适合新手。 浏览 Hacktoberfest issue

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

未关闭
  • 哪里不对？
#3,148 0 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看

维护者通常 2 天内回复

还没有人认领这个 Issue。

评估

难度
3/5
预计耗时
1-2 天
新手友好度
65/100
Issue 类型
缺陷
描述清晰度
描述清楚
活跃度
活跃
技术栈
cpp, postgresql
领域
backend, databases

调研方向

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.

由索引模型根据 Issue 内容生成。

描述

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 ! :)

主要语言
C++
星标
1.4k
派生
397
平均合并
2 天 2 小时
30 天内合并 PR
4

环境准备

从这里开始

  1. 先读完整个 Issue，再读项目的贡献指南。
  2. 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
  3. Fork 仓库，在一个分支上完成修改。
  4. 提交 Pull Request，并在描述里引用这个 Issue 编号。

pgRouting/pgrouting 的其他 Issue

查看 pgRouting/pgrouting 的全部 Issue

相似的 Issue

更多 C++ Issue

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。