1.bellman-ford
1 #include<iostream> 2 #define INF 1000000 3 using namespace std; 4 struct edge 5 { 6 int from,to,cost; 7 edge(){} 8 edge(int ff,int tt,int cc) 9 { 10 from=ff; 11 to=tt; 12 cost=cc; 13 } 14 }; 15 const int maxn=105; 16 const int maxe=10005; 17 int d[maxn]; 18 edge es[maxe]; 19 int v,e; 20 21 void bellman_ford(int s) 22 { 23 fill(d,d+v,INF); 24 d[s]=0; 25 while(true) 26 { 27 bool update=false; 28 for(int i=0;i<e;i++) 29 { 30 edge e=es[i]; 31 if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.cost) 32 { 33 d[e.to]=d[e.from]+e.cost; 34 update=true; 35 } 36 } 37 if(!update) break; 38 } 39 for(int i=0;i<v;i++) 40 { 41 cout<<d[i]<<endl; 42 } 43 } 44 //如果返回true则存在复圈 45 bool find_negative_loop() 46 { 47 fill(d,d+v,INF); 48 for(int i=0;i<v;i++) 49 { 50 for(int j=0;j<e;j++) 51 { 52 edge e=es[j]; 53 if(d[e.to]>d[e.from]+e.cost) 54 { 55 d[e.to]=d[e.from]+e.cost; 56 57 //如果第n次仍然更新了，则存在负圈 58 if(i==v-1) return true; 59 } 60 } 61 } 62 return false; 63 } 64 int main() 65 { 66 cin>>v>>e; 67 int from,to,cost; 68 for(int i=0;i<e;i++) 69 { 70 cin>>from>>to>>cost; 71 from--; 72 to--; 73 es[i]=edge(from,to,cost); 74 } 75 //cout<<find_negative_loop(); 76 bellman_ford(0); 77 return 0; 78 }
2.dijkstra
1 #include<bits/stdc++.h> 2 #define INF 1000000 3 using namespace std; 4 const int maxn=1010; 5 //邻接矩阵形式 6 int cost[maxn][maxn]; 7 int used[maxn]; 8 int d[maxn]; 9 int n; 10 int prev[maxn];//最短路上所有前驱结点 11 vector<int> get_path(int t) 12 { 13 vector<int> path; 14 for(;t!=-1;t=prev[t]) 15 path.push_back(t);//不断沿着prev[t]走直到t=s 16 reverse(path.begin(),path.end()); 17 return path; 18 } 19 void dijkstra(int s) 20 { 21 fill(d,d+n,INF); 22 fill(used,used+n,0); 23 fill(prev,prev+n,-1); 24 d[s]=0; 25 while(true) 26 { 27 int v=-1; 28 for(int u=0; u<n; u++) 29 { 30 if(!used[u]&&(v==-1||d[u]<d[v])) 31 { 32 v=u; 33 } 34 } 35 if(v==-1) break;//所有节点都计算完毕 36 used[v]=1; 37 for(int u=0; u<n; u++) 38 { 39 if(d[u]>d[v]+cost[v][u]) 40 { 41 d[u]=d[v]+cost[v][u]; 42 prev[u]=v; 43 } 44 } 45 } 46 for(int i=0; i<n; i++) 47 { 48 cout<<d[i]<<endl; 49 } 50 51 vector<int> path=get_path(n-1); 52 for(int i=0;i<path.size();i++) 53 { 54 cout<<path[i]<<" "; 55 } 56 } 57 58 int main() 59 { 60 cin>>n; 61 for(int i=0; i<n; i++) 62 { 63 for(int j=0; j<n; j++) 64 { 65 cin>>cost[i][j]; 66 } 67 } 68 dijkstra(0); 69 return 0; 70 } 71 /* 72 测试数据 教科书 P189 G6 的邻接矩阵 其中 数字 1000000 代表无穷大 73 6 74 1000000 1000000 10 100000 30 100 75 1000000 1000000 5 1000000 1000000 1000000 76 1000000 1000000 1000000 50 1000000 1000000 77 1000000 1000000 1000000 1000000 1000000 10 78 1000000 1000000 1000000 20 1000000 60 79 1000000 1000000 1000000 1000000 1000000 1000000 80 结果： 81 D[0] D[1] D[2] D[3] D[4] D[5] 82 0 1000000 10 50 30 60 83 */
3.堆优化的dijkstra
1 #include<iostream> 2 #include<vector> 3 #include<queue> 4 #define INF 1000000 5 using namespace std; 6 typedef pair<int,int> P; //first代表最短距离，second代表顶点的编号 7 //邻接表 8 struct edge 9 { 10 int to,cost; 11 edge(int tt,int cc) 12 { 13 to=tt; 14 cost=cc; 15 } 16 }; 17 const int maxn=105; 18 vector<edge> G[maxn]; 19 int d[maxn]; 20 int n; 21 void heap_dijkstra(int s) 22 { 23 fill(d,d+n,INF); 24 priority_queue<P,vector<P>,greater<P> > que; 25 que.push(P(0,s)); 26 d[s]=0; 27 while(!que.empty()) 28 { 29 P p=que.top(); 30 que.pop(); 31 int v=p.second; 32 if(p.first>d[v]) continue; 33 for(int i=0;i<G[v].size();i++) 34 { 35 edge e=G[v][i]; 36 if(d[e.to]>d[v]+e.cost) 37 { 38 d[e.to]=d[v]+e.cost; 39 que.push(P(d[e.to],e.to)); 40 } 41 } 42 } 43 for(int i=0;i<n;i++) 44 cout<<d[i]<<endl; 45 } 46 int main() 47 { 48 cin>>n; 49 int from,to,cost; 50 for(int i=0;i<n;i++) 51 { 52 cin>>from>>to>>cost; 53 from--; 54 to--; 55 G[from].push_back(edge(to,cost)); 56 G[to].push_back(edge(from,cost)); 57 } 58 59 heap_dijkstra(0); 60 return 0; 61 }
4.floyd_warshall
1 #include<iostream> 2 #include<memory.h> 3 #define INF 1000000 4 using namespace std; 5 const int maxn=105; 6 int d[maxn][maxn]; 7 int n; 8 //任意两点间的最短路问题,dp 9 void floyd_warshall() 10 { 11 for(int i=0; i<n; i++) 12 d[i][i]=0; 13 14 for(int k=0; k<n; k++) 15 for(int i=0; i<n; i++) 16 for(int j=0; j<n; j++) 17 d[i][j]=min(d[i][j],d[i][k]+d[k][j]); 18 19 for(int i=0; i<n; i++) 20 cout<<d[0][i]<<endl; 21 } 22 int main() 23 { 24 memset(d,INF,sizeof(d)); 25 cin>>n; 26 for(int i=0; i<n; i++) 27 for(int j=0; j<n; j++) 28 cin>>d[i][j]; 29 30 floyd_warshall(); 31 return 0; 32 }
5.spfa
1 #include<iostream> 2 #include<stdio.h> 3 #include<vector> 4 #include<queue> 5 using namespace std; 6 #define inf 99999999 7 typedef struct dd 8 { 9 int a,d; 10 }node; 11 int dis[20005],n; 12 vector<node> maps[20005]; 13 void sets() 14 { 15 for(int i=1;i<=n;i++) 16 { 17 dis[i]=inf; 18 } 19 } 20 void spfa() 21 { 22 queue<int> q; 23 int b[20005]={0},t;//b数组标识节点是否在队列中 24 q.push(1);//起点入队 25 b[1]=1; //标记 26 dis[1]=0; //距离 27 while(!q.empty()) 28 { 29 //队首元素出队 30 t=q.front(); 31 q.pop(); 32 //标记 33 b[t]=0; 34 //这个点作为起点的路径有多少 35 int len=maps[t].size(); 36 int a; 37 for(int i=0;i<len;i++) 38 { 39 //这条路径的终点 40 a=maps[t][i].a; 41 if(dis[a]>maps[t][i].d+dis[t]) 42 { 43 dis[a]=maps[t][i].d+dis[t]; 44 if(!b[a]) 45 { 46 b[a]=1; 47 q.push(a); 48 } 49 } 50 } 51 } 52 } 53 int main() 54 { 55 int m,a,b,l; 56 node Now; 57 while(scanf("%d%d",&n,&m)==2) 58 { 59 sets(); 60 while(m--) 61 { 62 scanf("%d%d%d",&a,&b,&l); 63 Now.a=b; 64 Now.d=l; 65 maps[a].push_back(Now); 66 } 67 spfa(); 68 for(int i=2;i<=n;i++) 69 { 70 printf("%d ",dis[i]); 71 } 72 } 73 return 0; 74 }