bellmanFord: runs in O(V²·E) rather than the O(V·E) / O(E) stated in README
评估
- 难度
- 2/5
- 预计耗时
- 1-3 小时
- 新手友好度
- 35/100
- Issue 类型
- 缺陷
- 描述清晰度
- 描述清楚
- 活跃度
- 停滞
- 技术栈
- javascript
调研方向
Start with bellmanFord.js lines 21–39 and inspect how it finds edges and handles each relaxation pass. The issue proposes iterating vertex.getEdges() and stopping when a pass makes no changes; check the linked pull request #2245 for work already underway. Done means the algorithm avoids repeated edge searches and exits early when a pass makes no changes, while preserving correct results.
由索引模型根据 Issue 内容生成。
描述
bellmanFord.js (lines 21–39) finds each edge again via graph.findEdge, which is a linear scan of the vertex's edge list, and has no early exit when a pass relaxes nothing. On complete digraphs with unit weights (a best-case input):
| V | node visits | visits / (V·E) | time |
|---|---|---|---|
| 20 | 79,420 | 10.4 | 3 ms |
| 40 | 1.28M | 20.5 | 10 ms |
| 80 | 20.5M | 40.5 | 136 ms |
| 160 | 327.6M | 80.5 | 1.8 s |
Fix: iterate vertex.getEdges() directly (this also fixes #2230) and stop when an iteration changes nothing.
Found during an independent property-based audit of this repo (full report and reproducible harness: https://github.com/devladpopov/algorithm-autopsy/tree/main/autopsy-02).
- 主要语言
- JavaScript
- 星标
- 197k
- 派生
- 31k
- PR 合并指标
- 30 天内没有已合并 PR
环境准备
- 没有 Dockerfile 或 Docker Compose 文件
- 没有 Pull Request 模板
- 阅读贡献指南
从这里开始
- 先读完整个 Issue，再读项目的贡献指南。
- 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
- Fork 仓库，在一个分支上完成修改。
- 提交 Pull Request，并在描述里引用这个 Issue 编号。
trekhleb/javascript-algorithms 的其他 Issue
-
难度 2/5 1-3 小时 新手友好度 78/100
trekhleb/javascript-algorithms#2231 ·
-
难度 2/5 1-3 小时 新手友好度 76/100
trekhleb/javascript-algorithms#2225 ·
-
BinarySearchTreeNode removing可能已有人在做 @bbonch 于 264 天前认领。 未关闭
难度 2/5 1-3 小时 新手友好度 72/100
trekhleb/javascript-algorithms#2102 · 1 条评论 ·
-
math: uniquePaths and leastCommonMultiple return non-integers below 2^53; iterative Euclid is subtraction-based and can hang可能已有人在做 @Shubham-Padkonde 于 7 天前认领。 未关闭
难度 3/5 1-2 天 新手友好度 35/100
trekhleb/javascript-algorithms#2238 ·
-
Trie.deleteWord fails for words containing characters outside the BMP (e.g. emoji)可能已有人在做 @Shubham-Padkonde 于 7 天前认领。 未关闭
难度 1/5 1 小时以内 新手友好度 35/100
trekhleb/javascript-algorithms#2237 ·
查看 trekhleb/javascript-algorithms 的全部 Issue
相似的 Issue
-
难度 1/5 1 小时以内 新手友好度 88/100
-
tech-debt
难度 2/5 1-3 小时 新手友好度 72/100
srikanth235/centraid#1155 ·
维护者通常 1 天内回复
-
难度 2/5 1-3 小时 新手友好度 85/100
维护者通常 1 天内回复
-
难度 2/5 1-3 小时 新手友好度 73/100
microsoft/monaco-editor#5563 ·
维护者通常 1 天内回复
-
难度 2/5 1-3 小时 新手友好度 85/100
维护者通常 1 天内回复