最短路径问题——（弗洛伊德算法与迪杰斯特拉算法）

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

最短路径问题——（弗洛伊德算法与迪杰斯特拉算法）【板子】

题目：

对于下面的图片所给出的关系,回答下面两个问题：

利用迪杰斯特拉算法求点A到每一个点之间的最小距离。
利用弗洛伊德算法求每两个点之间的最短路径。

（注意图中的A~E，分别用1~5来代替）

请添加图片描述

对于问题1（Dijkstra）：

第一行输入三个数n，m，q分别表示一共有n个点，m条边，q个查询

接下来的m行每行输入三个数i，j，x，其中i，j分别表示边的起点和终点，x表示这条边的距离

最后q行，每行输入一个数字表示查询点A到每一个点之间的最短距离。

输入样例：
5 7 3
1 2 6
1 5 4
2 5 1
2 3 2
3 5 3
3 4 2
4 5 6
输出样例：
5
7
4
对于问题2（Floyd）：

第一行输入三个数n，m，q分别表示一共有n个点，m条边，q个查询

接下来的m行每行输入三个数i，j，x，其中i，j分别表示边的起点和终点，x表示这条边的距离

最后q行，每行输入两个数字表示查询任意两个点之间的最短距离。

输入样例：
5 7 3
1 2 6
1 5 4
2 5 1
2 3 2
3 5 3
3 4 2
4 5 6
1 3
2 5
3 4
输出样例：
7
1
2

问题1（Dijkstra）：

// 最短路算法——迪杰斯特拉算法
#include<iostream>
#include<vector>
using namespace std;const int inf = 0x3f3f3f3f;
vector<int> dijkstra(vector<vector<int>> nums, int origin){int nsize = nums.size();vector<int> mk(nsize, 0);   // 标记数组 vector<int> ans(nsize, inf);for(int i = 1;i < nsize;i ++) ans[i] = nums[i][origin];ans[origin] = 0;  // 源点到源点的距离为0 mk[origin] = 1;  // 对源点进行标记for(int i = 1;i < nsize - 1;i ++){// 首先找到没有标记的短路程的点int idx = 0;  // ans[0] 的值是无穷大for(int i = 1;i < nsize;i++){if(!mk[i] && ans[i] < ans[idx]){idx = i;}}// 选出来之后进行标记 mk[idx] = 1;// 更新每一个举例for(int i = 1;i < nsize;i ++){if(ans[idx] + nums[idx][i] < ans[i]) ans[i] = ans[idx] + nums[idx][i];} }return ans;
}void solve(){// 使用int n;cin>>n; // 一共有n个点int m;cin>>m;  // 一共有m条边 int q;cin>>q;  // 一共有q个查询 vector<vector<int>> nums(n + 1, vector<int>(n + 1, inf));while(m--){int i,j,_x;cin>>i>>j>>_x;nums[i][j] = _x;nums[j][i] = _x;}vector<int> ans = dijkstra(nums, 1);//	for(auto v : ans){
//		cout<<v<<' ';
//	}
//	cout<<endl;// q次询问while(q--){int T;cin>>T;cout<<ans[T]<<endl;} return ;
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;while(t--){solve();}return 0;
}

问题1（Floyd）：

// 弗洛伊德算法
#include<iostream>
#include<vector>
using namespace std;
const int inf = 0x3f3f3f3f; vector<vector<int>> floyd(vector<vector<int>> nums){int nsize = nums.size();for(int k = 1;k < nsize;k++){   // 选择每一个点作为中间点进行更新 for(int i = 1;i < nsize;i ++){  for(int j = 1;j < nsize;j ++){if(nums[i][k] + nums[k][j] < nums[i][j]){nums[i][j] = nums[i][k] + nums[k][j];nums[j][i] = nums[i][j];   // 因为是无向边 }}}}return nums; }void solve(){// 使用int n;cin>>n; // 一共有n个点int m;cin>>m;  // 一共有m条边 int q;cin>>q;  // 一共有q个查询 vector<vector<int>> nums(n + 1, vector<int>(n + 1, inf));// 初始化自己到自己的距离为0for(unsigned i = 1;i < nums.size();i ++) nums[i][i] = 0; while(m--){int i,j,_x;cin>>i>>j>>_x;nums[i][j] = _x;nums[j][i] = _x;}vector<vector<int>> ans = floyd(nums);//	for(auto v : ans){
//		for(auto u : v){
//			cout<<u<<' ';
//		}
//		cout<<endl;
//	}
//	cout<<endl;// q次询问while(q--){int i,j;cin>>i>>j;cout<<ans[i][j]<<endl;} return ;
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;while(t--){solve();}return 0;
}