单源最短路问题(SSSP)常用的算法有DijkstraBellman-Ford，这两个算法进行优化就有了Dijkstra+heap、SPFA(Shortest Path Faster Algorithm)算法。这两个算法写起来非常相似下面就从他们的算法思路、写法和适用场景上进行对比分析。如果對最短路算法不太了解可先看一下相关ppt:

为了解释得简单点，以及让对比更加明显我就省略了部分细节。

-->队头出队松弛它的边

-->松弛了苴不在队内的点入队

• Dijkstra+heap是用小根堆，每次取出d最小的点来更新距离，那么这个点来说最小距离就是当前的d。
• SPFA是用双端队列每次取出队頭，来更新距离它之后可能还会入队。它是一种动态逼近法因为每次松弛距离都会减小，所以松弛一定会有结束的如果一个点入队超过n次就是存在负环。

如果是稠密图Dijkstra+heap比SPFA快。稀疏图则SPFA更快SPFA可以有SLF和LLL两种优化，SLF就是d比队头小就插入队头否则插入队尾。

另外Dijkstra和Prim也佷相似，它们的区别主要是d的含义前者是到s的临时最短距离，后者是到树的临时最短距离相同点是，每次找d最小的更新其它点的距离

单源最短路问题(SSSP)常用的算法有DijkstraBellman-Ford，这两个算法进行优化就有了Dijkstra+heap、SPFA(Shortest Path Faster Algorithm)算法。这两个算法写起来非常相似下面就从他们的算法思路、写法和适用场景上进行对比分析。如果對最短路算法不太了解可先看一下相关ppt:

为了解释得简单点，以及让对比更加明显我就省略了部分细节。

-->队头出队松弛它的边

-->松弛了苴不在队内的点入队

• Dijkstra+heap是用小根堆，每次取出d最小的点来更新距离，那么这个点来说最小距离就是当前的d。
• SPFA是用双端队列每次取出队頭，来更新距离它之后可能还会入队。它是一种动态逼近法因为每次松弛距离都会减小，所以松弛一定会有结束的如果一个点入队超过n次就是存在负环。

如果是稠密图Dijkstra+heap比SPFA快。稀疏图则SPFA更快SPFA可以有SLF和LLL两种优化，SLF就是d比队头小就插入队头否则插入队尾。

另外Dijkstra和Prim也佷相似，它们的区别主要是d的含义前者是到s的临时最短距离，后者是到树的临时最短距离相同点是，每次找d最小的更新其它点的距离