【蓝桥杯】最短路径Floyd算法原来如此简单

🍑前言：

☕☕学过《数据结构与算法》这门课的同学应该都知道求解最短路径的两大经典算法，“弗洛伊德”和“迪杰斯特拉”，笔者一直以为这两个高大上的算法我这种菜鸡肯定是学不会的啦，但是前两天看了看弗洛伊德算法的代码，没想到竟然如此简单！😛

🌻🌻Floyd算法是用来求解多源点最短路径问题的，算法基于动态规划实现，而且核心代码用三个for循环就能轻松搞定，代码简练，稍加理解就能轻松记住~

题目传送门：🚀🚀🚀

🍋Floyd算法模板：

👩🏻‍🏫了解Floyd之前先要知道什么是邻接矩阵，对于有n个节点的图，所谓矩阵其实就是二维数组graph[n][n]，用来描述节点之间的关系。其中graph[i][j] = x表示节点i与节点j之间存在一条边，边长为x（换句话说就是从节点i可以直接到节点j，且距离为x），如果i与j之间没有边，可以用graph[i][j] = 无穷大表示；当然如果节点到节点之间的路径是双向的，graph[i][j] = graph[j][i]。

📌构建好邻接矩阵，就可以使用Floyd算法了：

for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j];}}}

📑三个for循环加一行状态转移，最终的结果就是graph[i][j]中存储的值代表节点i到节点j的最短路径。

📑Floyd本质是动态规划的过程。状态转移方程：f[k][i][j] = min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j])，表示经过前k个点（包括k），从i到j的最小值。

📑模板中的dp只有i，j两个变量，是应为k可以进行状态压缩。

📑最终Floyd可以精简成四行代码~🍺

🍊实战演练：

👉🏻蓝桥杯2021填空题-路径：

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。

小蓝的图由 2021 个结点组成，依次编号 1 至 2021。

对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。

例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。

请计算，结点 1 和结点 2021 之间的最短路径长度是多少。

提示：建议使用计算机编程解决问题。

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

• 求最小公倍数可以先求最大公约数（辗转相除法）：

  public static int gcd(int a, int b) {    return b == 0 ? a : gcd(b, a % b);}

• Java中的距离无穷大可以用Double型的Double.POSITIVE_INFINITY表示，任何数加上无穷大还是无穷大。

• 记住Floyd的三个for循环，最外层是for (int k = 1; k <= n; k++)，这个顺序不能更改。

🍦AC代码（Java）：

import java.util.Arrays;public class Main {    public static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b);    }    public static int lcm(int a, int b) { return (a * b) / gcd(a, b);    }    public static void main(String[] args) { final int n = 2021; // 建立邻接矩阵 double[][] graph = new double[n + 1][n + 1]; // 距离无穷可以使用double表示 for (int i = 0; i < graph.length; i++)     Arrays.fill(graph[i], Double.POSITIVE_INFINITY); for (int i = 1; i < graph.length; i++)     graph[i][i] = 0; // 根据要求添入边权 for (int a = 1; a <= n; a++) {     for (int b = 1; b <= n; b++) {  if (a == b)      continue;  if (Math.abs(a - b) <= 21) {      int dis = lcm(a, b);      graph[a][b] = dis;  } else {      continue;  }     } } // Floyd最短路，经典三个for for (int k = 1; k <= n; k++) {     for (int i = 1; i <= n; i++) {  for (int j = 1; j <= n; j++) {      graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);  }     } } // 别忘了double要cast回int System.out.println((int)graph[1][2021]); // 结果：10266837    }    }

👉🏻力扣743题库-网络延迟时间：

• 还是用Floyd求出任意两点间的最短路径，最后在遍历一遍graph[k][i...n]，找到节点k到其他节点间最短路径的最大值。

🍦AC代码（Java）：

class Solution {    public int networkDelayTime(int[][] times, int n, int K) { int[][] graph = new int[n + 1][n + 1]; for (int[] ints : graph) { //这里无穷大用int型最大值表示     Arrays.fill(ints, Integer.MAX_VALUE); } for (int i = 1; i <= n; i++)     graph[i][i] = 0; for (int[] time : times) graph[time[0]][time[1]] = time[2]; for (int k = 1; k <= n; k++) {     for (int i = 1; i <= n; i++) {  for (int j = 1; j <= n; j++) {      // 距离无穷参与运算会溢出，要手动修改      graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j] < 0 ? Integer.MAX_VALUE : graph[i][k] + graph[k][j]);  }     } } int ans = Integer.MIN_VALUE; for (int i = 1; i <= n; i++) {     if (graph[K][i] == Integer.MAX_VALUE)  return -1;     ans = Math.max(ans, graph[K][i]); } return ans;    }}

🍌🍌🍌
Floyd模板短短四行代码就可以求出任意两点间的最短路径，代码简练，很容易记住，只需要注意三个for循环的顺序是k-->i-->j即可。
🍍🍍🍍
创作不易，如果觉得本文对你有所帮助的话请动动小手，给博主点个免费的赞吧。🙇🏻‍♀️
🍉🍉🍉
@作者：Mymel_晗，计科专业大学牲菜狗一枚，请大佬们多多关照~

365PC电脑装机网