Floyd算法是多源最短路算法,复杂度最高(n^3),通常用在点比较少的起点不固定的问题中。能解决负边(负权)但不能解决负环。 (暴力)
Dijkstra算法是单源最短路算法,最常用时间复杂度(n^2)优化后可以达到(nlogn),不能解决负边问题,稀疏图(点的范围很大但是边不多,边的条数|E|远小于|V|²)需要耗费比较多的空间。
SPFA算法适合稀疏图,可以解决带有负权边,负环的问题,但是在稠密图中效率比Dijkstra要低。 (稠密图 就是点多边少)
http://acm.hdu.edu.cn/showproblem.php?pid=2544
题目大意:输入a点输入b点输入权值c
求最短路
dijkstra做法
#include <iostream> #include<string.h> #include<algorithm> using namespace std; #define maxn 101 int g[maxn][maxn]; int dist[maxn]; int sure[maxn]; int n,m; void dijkstra(int begin) { memset(dist,0x3f3f3f,sizeof(dist)); memset(sure,0,sizeof(sure)); dist[begin]=0; while(1) { int i,u=-1,v; int min=0x3f3f3f; for(i=1;i<=n;i++) { if(!sure[i]&&dist[i]<min) //检查是否还有更短路线 { min=dist[i]; u=i; } } if(u==-1) break; sure[u]=1; for(v=1;v<=n;v++) { if(g[u][v]!=-1&&dist[v]>dist[u]+g[u][v]) //更新最短路线 { dist[v] = dist[u] + g[u][v] > dist[v] ? dist[v]: dist[u]+g[u][v]; //最小值 } } } } int main() { while(scanf("%d%d",&n,&m)&&(m&&n)) { int a,b,c; memset(g,-1,sizeof(g)); for(int i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); g[a][b] = c; g[b][a] = c; } dijkstra(1); printf("%d\n",dist[n]); } return 0; }
原文:https://www.cnblogs.com/AAAzhuo/p/11251404.html