最短路径——Floyd Dijsktra

本文主要是介绍最短路径——Floyd Dijsktra，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Floyd

算法核心：通过比较 已有的路径长度和通过中转点t到达目标点的长度来求出任意两点间最短路径

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int n , m , k;
int d[210][210];
int x , y , z;void floyd(){     //通过比较 已有的路径长度和通过中转点t到达目标点的长度来求出最短路径for(int t = 1 ; t<=n ; t++)     //将中转点t放在最外层循环，以保证每个d[x][y]都判断过每个中转点 (允许经过t个中转点的最短路径)for(int i = 1 ; i<=n ; i++)for(int j = 1 ; j<=n ; j++)d[i][j] = min(d[i][j] , d[i][t]+d[t][j]);
}int main(){cin>>n>>m>>k;memset(d , 0x3f , sizeof d); //初始化所有边为无穷大for(int i = 1 ; i<=n ; i++) d[i][i] = 0; //初始自环为0while(m--){cin>>x>>y>>z;d[x][y] = min(d[x][y] , z);}floyd();while(k--){cin>>x>>y;if(d[x][y]>1000000) cout<<"impossible"<<endl;else cout<<d[x][y]<<endl;}return 0;
}

Dijsktra算法

算法核心：一趟确定一个距离最近的点，再利用该点更新附近的点。以此求得一确定点到另一点的距离。

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f;bool flag[N];
int g[N][N];
int d[N];
int n,m;int Dijkstra(){memset(d , 0x3f , sizeof d);d[1]=0;     //第一个点的距离当然为零for(int i = 0 ; i<n ; i++ ){int t = -1;      //t记录当前访问的点 //因为第一趟t不确定所以设为-1 直到找到第一个不在确定集合中的点for(int j = 1 ; j<=n ; j++)if(!flag[j]&&(t==-1||d[t]>d[j]))t = j;flag[t]=true;   //列入确定集合for(int j = 1 ; j<=n ; j++)    //更新相邻点距离d[j] = min(d[j] , d[t]+g[t][j]);}if(d[n]==INF) return -1;return d[n];
}int main(){cin>>n>>m;memset(g,0x3f,sizeof g);while(m--){int x,y,z;cin>>x>>y>>z;g[x][y] = min(g[x][y],z);}int k = Dijkstra();cout<<k<<endl;}

堆优化版

#include <iostream>
#include <queue>
#include <cstring>using namespace std;const int N = 150010;int e[N] , w[N] , ne[N] , h[N] , idx;
int n , m;
int d[N];
bool st[N];typedef pair<int , int> PII;void add(int a, int b , int c)
{e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx++;
}int Dijkstra()
{memset(d , 0x3f , sizeof d);priority_queue<PII , vector<PII> , greater<PII>> heap;d[1] = 0;heap.push({0 , 1});while(heap.size()){auto t = heap.top();heap.pop();int ver = t.second , dist = t.first;if(st[ver]) continue;st[ver] = true;for(int i = h[ver] ; ~i ; i = ne[i]){int j = e[i];if(d[j] > dist + w[i])d[j] = dist + w[i] , heap.push({d[j] , j});}}if(d[n] == 0x3f3f3f3f) return -1;return d[n];
}int main()
{memset(h , -1 , sizeof h);cin >> n >> m;while(m--){int a , b , c;cin >> a >> b >> c;add(a , b , c);}cout << Dijkstra() << endl;return 0;
}