【运筹优化】最短路算法之SPFA算法 + Java代码实现

---

一、SPFA算法简介

SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同，为 O(VE)。

SPFA算法的全称是：Shortest Path Faster Algorithm，是西南交通大学段凡丁于 1994 年发表的论文中的名字。不过，段凡丁的证明是错误的，且在 Bellman-Ford 算法提出后不久（1957 年）已有队列优化内容，所以国际上不承认 SPFA 算法是段凡丁提出的。

---

二、SPFA算法思想

若给定的图存在负权边，类似Dijkstra算法等算法便没有了用武之地，SPFA算法便派上用场了。简洁起见，我们约定加权有向图G不存在负权回路，即最短路径一定存在。

用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

定理

只要最短路径存在，上述SPFA算法必定能求出最小值。证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。

实际上，如果一个点进入队列达到n次，则表明图中存在负环，没有最短路径。
段凡丁论文中的复杂度证明 （O(kE)，k 是小常数）是错误的，在此略去。该算法的最坏复杂度为 O(VE)。

对SPFA的一个很直观的理解就是由无权图的BFS转化而来。在无权图中，BFS首先到达的顶点所经历的路径一定是最短路(也就是经过的最少顶点数)，所以此时利用数组记录节点访问可以使每个顶点只进队一次，但在带权图中，最先到达的顶点所计算出来的路径不一定是最短路。一个解决方法是放弃数组，此时所需时间自然就是指数级的，所以我们不能放弃数组，而是在处理一个已经在队列中且当前所得的路径比原来更好的顶点时，直接更新最优解。

SPFA算法有两个优化策略SLF和LLL

SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，否则插入队尾；

LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出队进行松弛操作。SLF 和 LLF 在随机数据上表现优秀，但是在正权图上最坏情况为 O(VE)，在负权图上最坏情况为达到指数级复杂度。

---

三、Java代码实现

@Data
public class SPFA {// 距离矩阵double[][] distance;// 起点int start;// 终点int end;/*** @param distance* @param start* @param end* @Description 构造函数* @Author WSKH*/public SPFA(double[][] distance, int start, int end) {this.distance = distance;this.start = start;this.end = end;}/*** @Description 进行求解* @Author WSKH*/public void solve() {// 初始化dis一维数组double[] dis = new double[distance.length];for (int i = 0; i < dis.length; i++) {if (i != start) {dis[i] = Double.MAX_VALUE;}}// 声明队列(用集合模拟)List<Integer> list = new LinkedList<>();// 初始化队列，添加起点进入队列list.add(start);// 记录每个顶点入队的次数int[] counter = new int[distance.length];counter[start]++;//HashMap<Integer,List<Integer>> shortestPathMap = new HashMap<>();for (int i = 0; i < distance.length; i++) {List<Integer> arrayList = new ArrayList<>();arrayList.add(start);shortestPathMap.put(i,arrayList);}// 开始循环while (!list.isEmpty()) {// 获取当前队首元素索引int index = list.remove(0);// 看看能不能松弛for (int i = 0; i < dis.length; i++) {if (i != start && i != index && dis[i] > distance[index][i] + dis[index]) {dis[i] = distance[index][i] + dis[index];List<Integer> integerList = new ArrayList<>(shortestPathMap.get(index));integerList.add(i);shortestPathMap.put(i,integerList);// 看看i能不能入队if (!list.contains(i)) {list.add(i);counter[i]++;// 如果某个顶点入队次数大于顶点数，那么说明图中存在负权回路if (counter[i] > distance.length) {throw new RuntimeException("存在负权回路！" + Arrays.toString(counter));}}}}}System.out.println("每个顶点入队次数为：" + Arrays.toString(counter));System.out.println("起点到其余各个点的最短路为：" + Arrays.toString(dis));System.out.println(shortestPathMap.get(end));}
}

---

四、测试

public class Test {public static void main(String[] args) {double[][] distance = new double[][]{{0, 8, 9, 2, 5},{8, 0, 7, 2, 8},{9, 7, 0, 3, 9},{2, 2, 3, 0, 5},{5, 8, 9, 5, 0},};new SPFA(distance,0,2).solve();}
}

控制台输出：

每个顶点入队次数为：[1, 2, 2, 1, 1]
起点到其余各个点的最短路为：[0.0, 4.0, 5.0, 2.0, 5.0]
[0, 3, 2]

其中 [0, 3, 2] 代表0到2的最短路径为：0->3->2