求c++ 最精简的SPFA最短路径算法代码

答案:2 悬赏:60 手机版

解决时间 2021-03-24 01:45

提问者网友：半生酒醒
2021-03-23 15:47

最佳答案

五星知识达人网友：忘川信使
2021-03-23 16:21

为神马是0分。。
好吧我当回好人。。
其实SPFA没什么好精简的，复杂也复杂不起来。一个简易queue7、8行，存储结构几十行，核心代码几十行，不出90行肯定搞定。算法核心代码就一点点，整个SPFA程序其实是数据结构占了一半的代码量（别告诉我你想用邻接矩阵。。大图不爆内存就怪了。。）
据个人测试，小图（半年没搞OI了，具体多大的图我忘了）中前向星（也可以叫边集数组）和邻接表速度差不多，前向星主要是把时间用在排序上了。我排序这块比较渣顶多敲个堆排，前向星的排序直接就调用stdlib呢个qsort函数了。于是大图里前向星照我这么写就慢了很多，具体体现在某USACO的最短路径题，哪章我忘掉了。。我写的前向星有两组超时。要代码的话，Hi我一下，不太想贴出来丢人……或者留个邮箱，发给你。

全部回答

1楼网友：纵马山川剑自提
2021-03-23 17:27

spfa在稀疏图上快，因为是通过边来增广的。dijkstra在稠密图上快。因为是通过点来增广的。某些情况下dijkstra 加上堆优化，在处理大数据的时候会比spfa快很多；但是spfa在随机数据的综合表现中相比dijkstra优势还是比较大的。总而言之，各有所长。

我要举报

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息