Leetcode记录：Floyd算法

Floyd算法

小明喜欢去公园散步，公园内布置了许多的景点，相互之间通过小路连接，小明希望在观看景点的同时，能够节省体力，走最短的路径。给定一个公园景点图，图中有 N 个景点（编号为 1 到 N），以及 M 条双向道路连接着这些景点。每条道路上行走的距离都是已知的。

小明有 Q 个观景计划，每个计划都有一个起点 start 和一个终点 end，表示他想从景点 start 前往景点 end。由于小明希望节省体力，他想知道每个观景计划中从起点到终点的最短路径长度。 请你帮助小明计算出每个观景计划的最短路径长度。

这是经典的多源最短路径问题，Floyd算法对边的权值正负没有要求，都可以处理。Floyd算法核心思想是动态规划。

1. 定义 grid[i][j][k] = m 表示 节点i 到 节点j 以[1…k] 集合为中间节点的最短距离为m。
2. 递推公式分为两个情况：i到j的最短路径是否经过k，因此有： grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1]).
3. 初始化：初始化k=0来表示没有中间节点，i直接到达j的距离，如果没有i->j的边，距离则设为一个最大值100000.
4. 递推顺序：k在最外层，i，j在内循环即可.

• 数据结构与算法