任意两点间最短路径floyed算法

本文主要是介绍任意两点间最短路径floyed算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1、无向带权图如下：

 2、采用floyed算法手动计算出来的任意两点间最短路径数组：

3、采用floyed算法计算出来的任意两点间的最短路径：

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using namespace std;
 5 
 6 constexpr int INF = 0x3F;
 7 
 8 int floyed(vector<vector<int>> &graph, int from, int to) {
 9     int n = graph.size();
10     if (from > n - 1 || to > n - 1) {
11         return -1;
12     }
13     for (int k = 0; k < n; k++) {
14         for (int i = 0; i < n; i++) {
15             for (int j = 0; j < n; j++) {
16                 // 通过第k点作为中转节点,找出最短路径
17                 graph[i][j] = std::min(graph[i][j], graph[i][k] + graph[k][j]);
18             }
19         }
20     }
21     return graph[from][to];
22 }
23 
24 void buildGraph(int n, vector<vector<int>> &graph) {
25     for (int i = 0; i < n; i++) {
26         for (int j = 0; j < n; j++) {
27             std::cin >> graph[i][j];
28         }
29     }
30 }
31 void printGraph(const vector<vector<int>> &graph) {
32     for (const auto &vec : graph) {
33         for (const auto &val : vec) {
34             std::cout << val << " ";
35         }
36         std::cout << endl;
37     }
38 
39     std::cout << endl;
40 }
41 
42 int main()
43 {
44     FILE *fpIn;
45     fpIn = freopen("D:\\test.txt", "r", stdin);
46     if (fpIn == nullptr) {
47         std::cout << "freopen fail!" << endl;
48     }
49     int n = 0;
50     std::cin >> n;
51     vector<vector<int>> graph(n, vector<int>(n));
52     // 构建无向带权图
53     buildGraph(n, graph);
54     // 打印初始无向图带权图
55     printGraph(graph);
56     // 打印1到5的最短路径:
57     std::cout << floyed(graph, 1, 5) << endl;
58     // 打印通过floyed算法计算出来的任意两个节点间的最短路径图:
59     printGraph(graph);
60     fclose(fpIn);
61     system("pause");
62     return 0;
63 }

验证运行结果：

这篇关于任意两点间最短路径floyed算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！