找灵感的网站,幸运28网站建设,wordpress 重定向函数,企业建设网站公司文章目录 一、SPFA算法简介二、SPFA算法思想三、Java代码实现四、测试 一、SPFA算法简介
SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称#xff0c;通常用于求含负权边的单源最短路径#xff0c;以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同#xf… 文章目录 一、SPFA算法简介二、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 SLFSmall Label First 策略设要加入的节点是j队首元素为i若dist(j)dist(i)则将j插入队首否则插入队尾
LLLLarge 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;}}// 声明队列(用集合模拟)ListInteger list new LinkedList();// 初始化队列添加起点进入队列list.add(start);// 记录每个顶点入队的次数int[] counter new int[distance.length];counter[start];//HashMapInteger,ListInteger shortestPathMap new HashMap();for (int i 0; i distance.length; i) {ListInteger 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];ListInteger 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
