弗洛伊德最短路径

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

 时间复杂度为O（n*n*n） 结构简单，可以算任意两点间最短路径

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <fstream>
const int MAX = 1e4+10;
const int INF = 1e6;using namespace std;int d[MAX][MAX];
int V, E;void  Floyd(){for(int i=0; i<V; i++)for(int j=0; j<V; j++)for(int k =0; k<V; k++)d[j][k] = min(d[j][k], d[j][i]+d[i][k]);
}
//测试函数 
int main(){ifstream cin ("D:\\钢铁程序员\\程序数据\\003最短路径.txt");//从文件读取数据流，省去手动输入的麻烦 if(!cin){//读取如果失败 cout << "ERROR" << endl;}cin >> V >> E;for(int i=0; i<V; i++)for(int j=0; j<V; j++){if(i == j)d[i][j] = 0;elsed[i][j] = INF;}for(int i=0; i<E; i++){int a, b, c;cin >> a >> b >> c;d[a][b] = c;d[b][a] = c;}Floyd();cout << d[0][V-1] << endl;cin.close();//打开文件以后要关闭 return 0;
} 

 

这篇关于弗洛伊德最短路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---