luogu-dev / luogu-dev/cyaron

hack_spfa似乎不work

Open
#71 1 comment 0 reactions 0 assignees View on GitHub

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

  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.

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.