厦门网站模板,响应式网站制作教程,家装设计培训班哪里有,1688货源网今天的题目是回忆迷宫 这个题目我们来熟悉一下 弗洛伊德算法 的代码模板 弗洛伊德算法用来处理最短路径问题
弗洛伊德算法#xff08;Floyd’s algorithm#xff09;用于解决图中所有节点对之间的最短路径问题。算法的基本思路是通过逐步迭代更新节点对之间的最短路径长度Floyd’s algorithm用于解决图中所有节点对之间的最短路径问题。算法的基本思路是通过逐步迭代更新节点对之间的最短路径长度直到得到所有节点对之间的最短路径。
以下是弗洛伊德算法的大致思路 初始化距离矩阵创建一个二维矩阵称为距离矩阵用于存储节点对之间的最短路径长度。初始时距离矩阵的值为图中节点之间的直接距离如果两个节点之间没有直接边相连则距离为无穷大。 迭代更新最短路径通过遍历所有节点对于每一对节点 (i, j)检查是否存在一个中间节点 k使得从节点 i 到节点 j 经过节点 k 的路径长度比直接从 i 到 j 的路径更短。如果存在这样的中间节点 k则更新距离矩阵中节点 i 到节点 j 的最短路径长度为经过节点 k 的路径长度。 重复执行步骤 2重复执行步骤 2直到所有节点对之间的最短路径长度都被计算出来即距离矩阵不再变化。 输出结果输出距离矩阵其中的每个元素表示对应节点对之间的最短路径长度。
弗洛伊德算法的核心思想是动态规划。通过逐步迭代更新节点对之间的最短路径长度算法最终得到所有节点对之间的最短路径。由于需要遍历所有节点和中间节点算法的时间复杂度为 O(n^3)其中 n 是图中节点的数量。
总的来说就是建模核心的3个for循环
for (int k 1; k n; k) // 这个是中间途经的点{for (int i 1; i n; i) { // 起始点for (int j 1; j n; j) { // 终点d[i][j] min(d[i][j], d[i][k] d[k][j]);}}}最终实现的代码如下
#includeiostreamusing namespace std;
typedef long long ll;const int N 410;
ll d[N][N]; // 开辟一个数组存储信息int n, m, q; // 设置全局变量void floyd()
{for (int k 1; k n; k){for (int i 1; i n; i) {for (int j 1; j n; j) {d[i][j] min(d[i][j], d[i][k] d[k][j]);}}}
}int main()
{cin n m q;// 下面要进行初始化操作for (int i 1; i n; i) {for (int j 1; j n; j) {if (i j) d[i][j] 0;else d[i][j] LLONG_MAX / 2;}}while (m--){ll a, b, c;cin a b c;d[a][b] d[b][a] min(d[a][b], c);}floyd();while (q--){int a, b;cin a b;if (d[a][b] LLONG_MAX / 2) cout -1 endl;else cout d[a][b] endl;}return 0;
}
有一个小细节初始化数组的时候
d[a][b] d[b][a] min(d[a][b], c);这个要避免有重边
