Open yihozhang opened 4 years ago
当我使用在以下代码所生成的数据上跑SPFA的时候,我的SPFA程序一共进行了25,000次进队+访问边的操作。(正好是边数+点数,这正好是理论最优的复杂度)
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/
I see. 似乎需要把生成的图shuffle一下,并且貌似生成的是无向图?在这样的情况下10000个点需要大概入队+访问边200w次。希望如果可能的话可以更新一下文档,以造福之后遇到类似问题的同学。
当我使用在以下代码所生成的数据上跑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/