算法用途
这个算法，如其名：Shortest Path Fastest Algorithm，就是求最短路的算法。和 Dijkstra 一样，这是一个单源最短路算法。
算法原理
这个算法因为与贝尔曼福德（Bellman-Ford）算法比较相似，只是在它的算法的基础上进行了队列优化，因此也被嘲讽为“队列优化的贝尔曼福德”。
就是每次可以更新到一个节点的最短距离的时候，我们就更新它，并更新所有它能到达的子节点，直到没有节点需要被更新。
算法结果
算法运行结束后，将会得到一个处理好的数组 d d d，其中 d [ i ] d[i] d[i]代表从起点出发到节点 i i i的最短路长度。
算法实现
- 我们首先定义一个数组 d d d，代表我们选定的起点到其他各个点的距离最小值，将 d d d数组中除了起点以外的所有的元素都赋成INF（无限大）；
- 然后我们定义一个队列（先进先出），并将起点压入队列中，记录起点已经在队列中；
- 循环：取出一个节点（设为 u u u），枚举与之相连的节点（设为 v v v，并设 线 段 u v 的 长 度 为 w 线段uv的长度为w 线段uv的长度为w），如果：
- 发现 d [ u ] + w < d [ v ] d[u]+w
d[u]+w<d[v]
- 如果不满足 d [ u ] + w < d [ v ] d[u]+w
d[u]+w<d[v]
- 发现 d [ u ] + w < d [ v ] d[u]+w
请看图（啊啊啊啊啊这个破图我做了两天！！！要转载请注明出处！！！）。
例题
洛谷P3371 【模板】单源最短路径
P3371 【模板】单源最短路径
题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入输出格式
输入格式：
输出格式：
一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为）
输入输出样例
输入样例#1：
输出样例#1：
0 2 4 3
说明
时空限制：
1000ms,128M
数据规模：
样例说明：
这个题就是模板题，直接打好 SPFA 就行了。
CPP源代码
#include
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/211541.html原文链接：https://javaforall.net
