建设短视频网站,站长之家seo综合查询,具有价值的网站建设,平面设计必备软件适用范围#xff1a;给定的图存在负权边#xff0c;这时类似Dijkstra等算法便没有了用武之地#xff0c;而Bellman-Ford算法的复杂度又过高#xff0c;SPFA算法便派上用场了。 我们约定有向加权图G不存在负权回路#xff0c;即最短路径一定存在。当然#xff0c;我们可以… 适用范围给定的图存在负权边这时类似Dijkstra等算法便没有了用武之地而Bellman-Ford算法的复杂度又过高SPFA算法便派上用场了。 我们约定有向加权图G不存在负权回路即最短路径一定存在。当然我们可以在执行该算法前做一次拓扑排序以判断是否存在负权回路但这不是我们讨论的重点。 算法思想我们用数组d记录每个结点的最短路径估计值用邻接表来存储图G。我们采取的方法是动态逼近法设立一个先进先出的队列用来保存待优化的结点优化时每次取出队首结点u并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作如果v点的最短路径估计值有所调整且v点不在当前的队列中就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作直至队列空为止 期望的时间复杂度O(ke) 其中k为所有顶点进队的平均次数可以证明k一般小于等于2。 实现方法 建立一个队列初始时队列里只有起始点再建立一个表格记录起始点到所有点的最短路径该表格的初始值要赋为极大值该点到他本身的路径赋为0。然后执行松弛操作用队列里有的点作为起始点去刷新到所有点的最短路如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。 判断有无负环 如果某个点进入队列的次数超过N次则存在负环SPFA无法处理带负环的图 首先建立起始点a到其余各点的最短路径表格 首先源点a入队当队列非空时 、队首元素a出队对以a为起始点的所有边的终点依次进行松弛操作此处有b,c,d三个点此时路径表格状态为 在松弛时三个点的最短路径估值变小了而这些点队列中都没有出现这些点需要入队此时队列中新入队了三个结点b,c,d 队首元素b点出队对以b为起始点的所有边的终点依次进行松弛操作此处只有e点此时路径表格状态为 在最短路径表中e的最短路径估值也变小了e在队列中不存在因此e也要入队此时队列中的元素为cde 队首元素c点出队对以c为起始点的所有边的终点依次进行松弛操作此处有e,f两个点此时路径表格状态为 在最短路径表中ef的最短路径估值变小了e在队列中存在f不存在。因此e不用入队了f要入队此时队列中的元素为def 队首元素d点出队对以d为起始点的所有边的终点依次进行松弛操作此处只有g这个点此时路径表格状态为 在最短路径表中g的最短路径估值没有变小松弛不成功没有新结点入队队列中元素为fg 队首元素f点出队对以f为起始点的所有边的终点依次进行松弛操作此处有deg三个点此时路径表格状态为 在最短路径表中eg的最短路径估值又变小队列中无e点e入队队列中存在g这个点g不用入队此时队列中元素为ge 队首元素g点出队对以g为起始点的所有边的终点依次进行松弛操作此处只有b点此时路径表格状态为 在最短路径表中b的最短路径估值又变小队列中无b点b入队此时队列中元素为eb队首元素e点出队对以e为起始点的所有边的终点依次进行松弛操作此处只有g这个点此时路径表格状态为 在最短路径表中g的最短路径估值没变化松弛不成功此时队列中元素为b 队首元素b点出队对以b为起始点的所有边的终点依次进行松弛操作此处只有e这个点此时路径表格状态为 在最短路径表中e的最短路径估值没变化松弛不成功此时队列为空了 最终a到g的最短路径为 (⊙v⊙)嗯 代码 1 #include2 #include3 #include 4 using namespace std;5 6 const int MAXN1001;7 const int INF999999;8 9 int map[MAXN][MAXN];//记录权值
10 int path[MAXN];//记录路径
11 int dis[MAXN];//记录最短值
12 int team[MAXN];//队列
13 bool visit[MAXN];//是否在队列中
14 int n,m,u,v,len,a,e;
15
16 void sc(int u)//求最短路径
17 {
18 int head0,tail1,p;
19 team[head]u;//队列的第一个为起点
20 path[u]u;//路径为起点
21 visit[u]true;//标记为已在队列中
22 dis[u]0;//起点的权值为0
23 while(headdis[p]map[p][i])//松弛
24 {
25 dis[i]dis[p]map[p][i];
26 path[i]p;
27 if(!visit[i])//如果不在队列中重新入队
28 {
29 team[tail]i;
30 visit[i]true;//标记已为在队列中
31 }
32 }
33 }
34 visit[p]false;//将p标记为没在队列中
35 head;//head后移head所指向的元素依次出队
36 }
37 cout1;i--)//输出路径
38 {
39 if(i!1)//避免最后一个路径带有--
40 cout;
41 else
42 coutnm;
43 for(int i1;in;i)//初始化
44 for(int j1;jn;j)
45 map[i][j]INF;
46 for(int i1;im;i){
47 cinuvlen;
48 map[u][v]len;
49 }
50 for(int i1;in;i)
51 dis[i]INF;
52 memset(visit,false,sizeof(visit));
53 memset(team,0,sizeof(team));
54 cinae;//输入查找的起点和终点
55 sc(a);
56 out(a,e);
57 return 0;
58 } ps可以用邻接表实现效率更高邻接矩阵容易炸空间。。。 自己选的路跪着也要走完 转载于:https://www.cnblogs.com/wsdestdq/p/6697605.html
