刚刚AC的pj普及组第四题就是一种单源最短路。
我们知道当一个图存在负权边时像Dijkstra等算法便无法实现;
而Bellman-Ford算法的复杂度又过高O(V*E),SPFA算法便派上用场了。
其实SPFA 是用队列的优化,过程详见下图(PS:图片转自网络)
好了,以上图片基本已经说明的SPFA的过程,下面就是代码实现:
模板如下:
void spfa(){ ; i<=n; i++) dis[i]=INF; //初始化 dis[start]=; inq[start]=; q.push(start); int i, v; while (!q.empty){ v=q.front(); // 取队首节点 q.pop(); inq[v]=; //释放节点,因为这节点可能下次被其他节点松弛,重新入队 ; i<=n; i++) //枚举所有顶点 && dis[i]>dis[v]+a[v][i]){ //判断 dis[i] = dis[v]+a[v][i]; //修改 if (!inq[i]){ // 如果扩展结点i不在队列中,入队 q.push(i); vis[i]=; } } } }
可以看到,因为维护队列,和bfs有其曲同工之妙,但有一点不同!!!
bfs一旦入队,哪怕后面出队也无法在入队,而SPFA不同。
从数组名vis[i](BFS),inq[i](SPFA)可以看出定义不同。
那么对于有负权边,SPFA时间会大大增加……
不难想到DFS会不会快一点(好吧,既然都说了,肯定快,233)。
大约是O(E)。
代码如下:
void spfa(now){//DFS ; i<=edge[now]; i++) //枚举从顶点now发出的边 if (dis[to[now][i]>dis[now]+a[now][to[now][i]]){ dis[to[now][i]=dis[now]+a[now][to[now][i]]; spfa(to[now][i]);//继续DFS } }
我们知道DFS其实是遍历到终点才换成另一条路,因此可以用来判断负权边!!
只需判断是否回到之前的节点即可,可以用 vis[i] bool数组记录。
再看看Bellman-Ford算法,思路太简单,枚举点和边,就是时间比较长,为O(VE)。
代码如下:(转自百度百科)
#include<iostream> #include<cstdio> using namespace std; #define MAX 0x3f3f3f3f #define N 1010 int nodenum, edgenum, original; //点,边,起点 typedef struct Edge //边 { int u, v; int cost; }Edge; Edge edge[N]; int dis[N], pre[N]; bool Bellman_Ford() { ; i <= nodenum; ++i) //初始化 dis[i] = (i == original ? : MAX); ; i <= nodenum - ; ++i) ; j <= edgenum; ++j) if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛(顺序一定不能反~) { dis[edge[j].v] = dis[edge[j].u] + edge[j].cost; pre[edge[j].v] = edge[j].u; } ; //判断是否含有负权回路 ; i <= edgenum; ++i) if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost) { flag = ; break; } return flag; } void print_path(int root) //打印最短路的路径(反向) { while(root != pre[root]) //前驱 { printf("%d-->", root); root = pre[root]; } if(root == pre[root]) printf("%d\n", root); } int main() { scanf("%d%d%d", &nodenum, &edgenum, &original); pre[original] = original; ; i <= edgenum; ++i) { scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost); } if(Bellman_Ford()) ; i <= nodenum; ++i) //每个点最短路 { printf("%d\n", dis[i]); printf("Path:"); print_path(i); } else printf("have negative circle\n"); ; }
看到核心部分,不难想到外层i跟内层循环无关,因此可以优化,即如果内层无松弛,可以提前结束!
这样一来,速度还是可以的……
之后我们看看dijkstra算法,其实就是贪心。
dis数组用来储存起始点到其他点的最短路。
转移方程为:
dis[i]=min(dis[i],dis[j]+w[j][i]|j为i能到达的点)
一开始dis[i]=INF,dis[start]=0;
很显然,不能处理有负边的情况……
时间为(V^2).两层循环解决。
注意每次选用没更新过的离源点最近的点对外拓展。
代码如下:
#include<stdio.h> #include<stdlib.h> #define INF 1<<28 #define N 1000+5 int a[N][N]; int d[N]; bool vis[N]; int i,j,k; int m;//m代表边数 int n;//n代表点数 int main() { scanf("%d%d",&n,&m); int mn; int x,y,z; ;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); a[x][y]=a[y][x]=z; } ;i<=n;i++) d[i]=INF; ;i<=m;i++) { mn=INF; ;j<=n;j++) if(!vis[j]&&d[j]<mn) { mn=d[j]; k=j; } vis[k]=; ;j<=n;j++) &&d[j]>d[k]+a[k][j]) d[j]=d[k]+a[k][j]; } ;i<=n;i++) printf("%d ",d[i]); ; }
最后用最最最最……最智障的floyd算法结束今天学习(完全是为了凑齐四种算法,基本没啥可说)
直接看核心代码
; k<=n; k++) ; i<=n; i++) ; j<=n; j++) { if(w[i][j]>w[i][k]+w[k][j]) w[i][j]=map1[i][k]+w[k][j]; }
注意最外层是循环中间的点!!!
其他就比较简单,不解释了,ok!