Floyd算法 是一种用于寻找给定的加权图中多源点之间最短路径的算法。
#include<stdio.h> #include<stdlib.h> #define max 1000000000 int d[1000][1000]; int main() { int i,j,k,m,n; int x,y,z; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) for(j=1;j<=n;j++) d[i][j]=max; for(i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); d[x][y]=z; d[y][x]=z; } for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(d[i][k]+d[k][j]<d[i][j]) d[i][j]=d[i][k]+d[k][j]; } for(i=1;i<=m;i++) printf("%d",d[1][i]); return 0; }
dijkstra算法 是一种用于寻找给定的加权图中单源点有向图中最短路径问题。
#include<stdio.h> #include<stdlib.h> #define max 11000000000 inta[1000][1000]; intd[1000];//d表示某特定边距离 intp[1000];//p表示永久边距离 inti,j,k; intm;//m代表边数 intn;//n代表点数 intmain() { scanf("%d%d",&n,&m); intmin1; intx,y,z; for(i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); a[x][y]=z; a[y][x]=z; } for(i=1;i<=n;i++) d[i]=max1; d[1]=0; for(i=1;i<=n;i++) { min1=max1; for(j=1;j<=n;j++) if(!p[j]&&d[j]<min1) { min1=d[j]; k=j; } p[k]=j; for(j=1;j<=n;j++) if(a[k][j]!=0&&!p[j]&&d[j]>d[k]+a[k][j]) d[j]=d[k]+a[k][j]; } for(i=1;i<n;i++) printf("%d->",p[i]); printf("%d ",p[n]); return 0; }
Bellman-ford算法 求含负权图的单源最短路径算法，效率很低
#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() { for(int i = 1; i <= nodenum; ++i) //初始化 dis[i] = (i == original ? 0 : MAX); for(int i = 1; i <= nodenum - 1; ++i) for(int j = 1; 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; } bool flag = 1; //判断是否含有负权回路 for(int i = 1; i <= edgenum; ++i) if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost) { flag = 0; break; } return flag; } void print_path(int root) //打印最短路的路径（反向） { while(root != pre[root]) //前驱 { printf("%d-->", root); root = pre[root]; } if(root == pre[root]) printf("%d ", root); } int main() { scanf("%d%d%d", &nodenum, &edgenum, &original); pre[original] = original; for(int i = 1; i <= edgenum; ++i) { scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost); } if(Bellman_Ford()) for(int i = 1; i <= nodenum; ++i) //每个点最短路 { printf("%d ", dis[i]); printf("Path:"); print_path(i); } else printf("have negative circle "); return 0; }
SPFA（Shortest Path Faster Algorithm）（队列优化）算法 求单源最短路径的一种算法，在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法
#include <iostream> #include <deque> #include <stack> #include <vector> using namespace std; const int MAXN=100; const int INF=0x7FFFFFFF; struct edge { int to,weight; }; vector<edge> adjmap[MAXN];//邻接表 bool in_queue[MAXN];//顶点是否在队列中 int in_sum[MAXN];//顶点入队次数 int dist[MAXN];//源点到各点的最短路径 int path[MAXN];//存储到达i的前一个顶点 int nodesum;//顶点数 int edgesum;//边数 bool SPFA(int source) { deque<int> dq; int i,j,x,to; for(i=1;i<=nodesum;i++) { in_sum[i]=0; in_queue[i]=false; dist[i]=INF; path[i]=-1; } dq.push_back(source); in_sum[source]++; dist[source]=0; in_queue[source]=true; //初始化完成 while(!dq.empty()) { x=dq.front(); dq.pop_front(); in_queue[x]=false; for(i=0;i<adjmap[x].size();i++) { to=adjmap[x][i].to; if((dist[x]<INF)&&(dist[to]>dist[x]+adjmap[x][i].weight)) { dist[to]=dist[x]+adjmap[x][i].weight; path[to]=x; if(!in_queue[to]) { in_queue[to]=true; in_sum[to]++; if(in_sum[to]==nodesum) return false; if(!dq.empty()) { if(dist[to]>dist[dq.front()]) dq.push_back(to); else dq.push_front(to); }else dq.push_back(to); } } } } return true; } void Print_Path(int x) { stack<int> s; int w=x; while(path[w]!=-1) { s.push(w); w=path[w]; } cout<<"顶点1到顶点"<<x<<"的最短路径长度为："<<dist[x]<<endl; cout<<"所经过的路径为：1"; while(!s.empty()) { cout<<s.top()<<""; s.pop(); } cout<<endl; } int main() { int i,s,e,w; edge temp; cout<<"输入顶点数和边数："; cin>>nodesum>>edgesum; for(i=1;i<=nodesum;i++) adjmap[i].clear();//清空邻接表 for(i=1;i<=edgesum;i++) { cout<<"输入第"<<i<<"条边的起点、终点还有对应的权值："; cin>>s>>e>>w; temp.to=e; temp.weight=w; adjmap[s].push_back(temp); } if(SPFA(1)) { for(i=2;i<=nodesum;i++) Print_Path(i); } else cout<<"图中存在负权回路"<<endl; return 0; }