三种算法 都是最短路 经典的算法, 三者的复杂度依次为 O(n)^2 O (n)^3 O(n)^2
可以看到,Floyd 复杂度最大 一般处理100 以内的数据左右
三种算法的适用范围:
Dijkstra：适用于权值为非负的图的单源最短路径，用斐波那契堆的复杂度O(E+VlgV)
SPFA：适用于权值有负值，且没有负圈的图的单源最短路径，论文中的复杂度O(kE)，k为每个节点进入Queue的次数，且k一般<=2，但此处的复杂度证明是有问题的，其实SPFA的最坏情况应该是O(VE). Floyd：每对节点之间的最短路径。 (1)当权值为非负时，用Dijkstra。 (2)当权值有负值，且没有负圈，则用SPFA，SPFA能检测负圈，但是不能输出负圈。 (3)SPFA检测负环：当存在一个点入队大于等于V次，则有负环， 先给出三种算法的 模板 我们要注意 在 数组 (邻接矩阵))初始化 以及在输入数据时 :如果是 无向图 则 应该是 map[x][y]=map[y][x]=s;
如果是 有向图 则 应该是 map[x][y]=s;
以及在初始化时 if(i==j) map[i][j]=0 或 map[i][j]=1(如果下面用到的是 乘积);
Dijstra /* Dijkstra 算法 模板 */ const int MAX=1<<29; const int N= 1000; int map[N][N];//邻接矩阵 int dist[N];//更新点 bool vis[N];//设置已访问 int n,m; void Dijkstra(int x)//x 为 起始点 { int i,j,mid,u; for(i=0;i<n;i++) { dist[i]=map[x][i]; vis[i]=false; } vis[x]=true;//起点已访问 dist[x]=0; for(j=2;j<=n;j++) { mid=MAX; u=0; for(i=0;i<=n;i++) { if(!vis[i]&&dist[i]<mid) { mid=dist[i]; u=i; } } vis[u]=true; for(i=0;i<=n;i++) { if(!vis[i]&&dist[u]+ma[u][i]<dist[i]) dist[i]=dist[u]+ma[u][i];//更新 } } } int main() { for(i=0;i<=n;i++) for(j=0;j<=n;j++) { if(i==j) map[i][j]=0;// 自己到自己 距离为0； else map[i][j]=MAX; //初始化最大 } /* 输入数据时 如果是 无向图 邻接矩阵应该是 map[x][y]=map[y][x]=z; 如果是有向图 则应该是map[x][y]=z; */ } Floyd 模板 /* Floyd 算法模板 */ for(k=0;k<n;k++) { for(i=0;i<n;i++) { for(j=0;j<n;j++) if(map[i][j]>(map[i][k]+map[k][j])) { map[i][j]=map[i][k]+A[k][j]; } // if(判断) } } SPFA 算法 用到的是 queue 队列 // SPFA 算法模板 queue #include<stdio.h> #include<queue> bool vis[N]; void SPFA(int s) { queue<int>Q; for(int i=0; i<=n; i++) dis[i]=MAX; //初始化每点i到s的距离 dis[s]=0; vis[s]=1; //设置访问 Q.push(s); //队列初始化,s为起点 压入队列 int i, v; while (!Q.empty()) { //队列非空 v=Q.front();//取队 头 Q.pop(); // 释放队首结点，因为这节点可能下次用来松弛其它节点，重新入队 for(i=0; i<=n; i++) //对所有顶点 if (dis[i]>dis[v]+map[v][i]) { dis[i] = dis[v]+map[v][i]; //修改最短路 if (!vis[i]) { //如果扩展结点i不在队列中，入队 vis[i]=true;//设置访问 Q.push(i); } } } } 三种算法的具体 理解思路 可以看下下面 的博客 Dijstra and Floyd : http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html SPFA : http://blog.csdn.net/muxidreamtohit/article/details/7894298 下面是 poj的 一些 最短路 题目
POJ 2387 1797 3268 Dijstra
POJ 3259 2240 Floyd 3660 1511 2502
poj 2387 : http://poj.org/problem?id=2387 经典 Dijstra 直接套模板
poj 1797 : http://poj.org/problem?id=1797 Dijstra 变形, 修改判断条件 找最小里面的最大 max(min(a,b),c);
poj 3268 : http://poj.org/problem?id=3268 也是Dijstra 调用两次Dijstra 一个来一个去 或 矩阵置换;
poj 3259: http://poj.org/problem?id=3259 虫洞问题, 可以用Floyd 用到负权值, 需要负 ;
poj 2240: http://poj.org/problem?id=2240 美元兑换问题 可以用spfa 或者floyd; 只要 最后兑换到自己 大于1.0 则yes 否则no ;
传送门:
poj 2387 : http://blog.csdn.net/pingjijnming/article/details/60574074
poj 1797 : http://blog.csdn.net/pingjijnming/article/details/60777478 poj 3268 : http://blog.csdn.net/sizaif/article/details/60964043 poj 3259: http://blog.csdn.net/sizaif/article/details/60964517 poj 2240: http://blog.csdn.net/sizaif/article/details/60963759