最短路问题---AngelNH

过去我也有美梦来着，有幻想来着，可不知神魔时候，都烟消云散了，还是遇见你之前的事。

Floyd算法理论

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。

Floyd算法理解起来最简单。

Floyd算法自我感觉是暴力+贪心的算法，把每一种可能都遍历一遍，在加上动态规划状态转移，把每一种遍历的结果与当前结果比较，如果遍历结果距离小于目前结果，则前一状态转移到的这一状态。

简单的说，如果 I 经过 K 到 J 的距离 小于 I 直接到 J 的 距离 ， 则I 到J 的距离 为 I 经过 K 到 J 的距离 。

例如：有如下有向图，利用Floyd算法，给出每一对顶点之间的最短路径及其路径长度求解过程中的变化。

闲来无聊，就做个GIF图片。

第一步：0行0列不变，依次填入表格。

第二步：遍历其余表格，十字交叉，看两个值相加是否小于当前值，小于则填入，否则，不变。直到遍历所有表格。

第三步：将更新后表格的1行1列不变依次填入，重复步骤二。

直到N行N列

结束

就拿动态图中的蓝色5，根据十字交叉，与红色分别相交于1和3 ，1+3=4<5,所以更新列表，将4填入。

代码

代码之前先看几道简单的OJ题

hdu最短路

hdu畅通工程续

Floyd最短路

只要稍微改下输入输出就可以AC。

以上是三道水题，水水更开心。

#include<iostream> #include<algorithm> using namespace std; int n,m; int mp[1005][1005]; int main() { while(cin>>n>>m&&n&&m) { for(int i =1;i<=n;++i) { for(int j=1;j<=n;++j) { if(i!=j) mp[i][j] = 1e9; else mp[i][j] = 0; } } int a,b,c; for(int i =1;i<=m;++i) { cin>>a>>b>>c; if(mp[a][b]>c) { mp[a][b] = c; mp[b][a] = c; } } for(int k =1;k<=n;++k) { for(int i = 1;i<=n;++i) { for(int j =1;j<=n;++j) { if(mp[i][k]+mp[k][j]<mp[i][j]) { mp[i][j] = mp[i][k]+mp[k][j]; } } } } for(int i =1;i<=n;++i) { for(int j =1;j<=n;++j) { cout<<mp[i][j]<<" "; } cout<<endl; } } }Dijstra算法

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。【来自百度百科】

Dijkstra算法虽然好，但是并不能解决负权问题，更准确的说是判断有没有负权的存在。

这个代码在学离散的时候，手动实现过，考试也考过，只是代码没写过，~纠结。

代码

hdu最短路

#include <iostream> using namespace std; #define inf 0x3f3f3f3f int map[105][105],dis[105],vis[105]; //map存地图，dis存源点到当前点的距离，vis存访问状态 int n,m; void dijkstra(int start) { int i,j,k; for(i=1; i<=n; i++) { dis[i]=map[start][i]; //对dis进行初始化 } for(i=1;i<=n;i++) vis[i]=0; //0表示没有被访问，1表示被访问 vis[start]=1; for(i=1;i<=n-1;i++) //因为最多访问n-1个点，所以循环n-1次 { int mix=inf; int u; for(j=1;j<=n;j++) { if(vis[j]==0 && mix>dis[j]) { mix=dis[j]; //记录下距离源点最近的点，并且没有被访问 u=j; } } vis[u]=1; //标记为已经被访问 for(k=1;k<=n;k++) { if(vis[k]==0 && dis[k]>dis[u]+map[u][k]) dis[k]=dis[u]+map[u][k]; //以该点为跳板，对所有点进行松弛 } } } int main() { int i,j,k; while(cin>>n>>m && n || m) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(i==j) map[i][j]=0; else map[i][j]=inf; //初始化 } while(m--) { int x,y,z; cin>>x>>y>>z; if(map[x][y]>z) { map[x][y]=map[y][x]=z; //无向图 } } dijkstra(1); cout<<dis[n]<<endl; } return 0; }#include<iostream> #include<cstring> using namespace std; #define Max 1e9 int n,m; int mp[10005][10005]; int dis[10005],visit[10005]; int main() { while(cin>>n>>m)//n条边 m个顶点 { for(int i =1;i<=m;++i) { mp[i][i] = 0; for(int j=1;j<i;++j) { mp[i][j] = mp[j][i] = Max; } } int a,b,c; for(int i=1;i<=n;++i) { cin>>a>>b>>c; if(mp[a][b]>c) mp[a][b] = mp[b][a] = c; } for(int i =1;i<=m;++i) { dis[i] = mp[1][i]; } memset(visit,0,sizeof(visit)); int Min,k; visit[1]=1; for(int i =1;i<=m;++i) { Min = Max; k = 1; for(int j =1;j<=m;++j) { if(visit[j]==0&&Min>dis[j]) { Min = dis[j]; k = j; } } visit[k] = 1; for(int j =1;j<=m;++j) { if(visit[j]==0&&dis[j]>dis[k]+mp[k][j]) dis[j] = dis[k] + mp[k][j]; } } cout<<dis[m]<<endl; } return 0; }Bellman_Fod算法

贝尔曼-福特算法（英语：Bellman–Ford algorithm），求解单源最短路径问题的一种算法，由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达。但算法可以进行若干种优化，提高了效率。

hdu最短路

#include <iostream> using namespace std; #define inf 0x3f3f3f3f #define max 10000 int u[2*max+10],v[2*max+10],w[2*max+10],dis[105]; int main() { //u存起点，v存终点，w存权值，dis和迪杰一样，由于是无向图，所以要 *2 int n,m,i,j,k; int x,y,z; while(cin>>n>>m && n || m) { for(i=1; i<=2*m; i++) { cin>>x>>y>>z; u[i]=x; v[i]=y; w[i]=z; j=i+1; //构造无向图 u[j]=y; v[j]=x; w[j]=z; i++; } for(i=1; i<=n; i++) dis[i]=inf; dis[1]=0; //将起点设置为零，这样可以保证从起点开始松弛 for(k=1; k<=n-1; k++) { //最多循环n-1次 for(i=1; i<=2*m; i++) { if(dis[v[i]]>dis[u[i]]+w[i]) dis[v[i]]=dis[u[i]]+w[i]; //对所有的边进行松弛操作 } } for(i=1; i<=2*m; i++) { if(dis[v[i]]>dis[u[i]]+w[i]) return false; //这里检测有没有负权，不过本题用不到 } cout<<dis[n]<<endl; } return 0; }#include<iostream> #include<vector> #include<algorithm> using namespace std; vector<int > v[20000005]; int dis[1000005]; int main() { int n , m,x,y,w; while(cin>>n>>m) { for(int i=0;i<10005;++i) dis[i] = 1e9; for(int i=0;i<n;++i) { cin>>x>>y>>w; v[i].push_back(x); v[i].push_back(y); v[i].push_back(w); } dis[0] = 0; dis[1] = 0; for(int i=1;i<n;++i) { for(int j=0;j<m;++j) { if(dis[v[j][0]]+v[j][2]<dis[v[j][1]]) { dis[v[j][1]] = dis[v[j][0]]+v[j][2]; } } } for(int i =2;i<=n;++i) { cout<<dis[i]<<" "; } } return 0; } ---来自腾讯云社区的---AngelNH