hack_spfa似乎不work
Nobody has claimed this yet.
- Dominant language
- Python
- Stars
- 1.7k
- Forks
- 182
- PR merge metrics
- No merged PRs in 30d
Description
当我使用在以下代码所生成的数据上跑SPFA的时候,我的SPFA程序一共进行了25,000次进队+访问边的操作。(正好是边数+点数,这正好是理论最优的复杂度)
```python
with open("test-spfa-10000-cyaron", "w") as f:
g = Graph.hack_spfa(10000, weight_limit = 20)
f.write("10000 15000\n")
for e in g.iterate_edges():
f.write("%d %d %d\n" % (e.start - 1, e.end - 1, e.weight))
````
作为对比,我构造的一个一万个点三万条边的图会进行47,005,310次操作。另外加了SLF优化的代码在cyaron生成的数据上进行了312,772(~10x SPFA)次操作,而堆优化的Dijkstra进行了25,044次操作。
任何关于hack_spfa的使用技巧和insight?
这是我构造的数据:https://paste.ubuntu.com/p/BSH873sdrN/
这是我的SPFA程序:https://paste.ubuntu.com/p/dGWJHnHQws/
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reproducing the reported results with Graph.hack_spfa(10000, weight_limit=20), the supplied graph data, and the linked SPFA program. Compare the generated graph's operations with the reported 25,000 and 312,772 counts, then determine whether the behavior is expected or indicates a defect; done means the behavior is explained or the issue is fixed and verified.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- tooling
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100