-
Notifications
You must be signed in to change notification settings - Fork 167
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
hack_spfa似乎不work #71
Comments
I see. 似乎需要把生成的图shuffle一下,并且貌似生成的是无向图?在这样的情况下10000个点需要大概入队 访问边200w次。希望如果可能的话可以更新一下文档,以造福之后遇到类似问题的同学。 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
当我使用在以下代码所生成的数据上跑SPFA的时候,我的SPFA程序一共进行了25,000次进队 访问边的操作。(正好是边数 点数,这正好是理论最优的复杂度)
作为对比,我构造的一个一万个点三万条边的图会进行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/
The text was updated successfully, but these errors were encountered: