简介
最近图论+最短路的题比较多，总结一下三种求最短路的python模板：bellman-ford、dij、floyd算法
1. Bellman-ford：单源最短路
核心思想：动态规划，考虑源点src到任意节点j中间的边数
从源点src到j经过k条边的最短路 = min(从源点src到i经过k - 1条边的最短路 + i到j经过一条边的最短路)
dp[k][j]表示从源点src到j经过k条边的最短路；依次计算边数为1的最短路，边数为2的最短路，......，边数为n - 1的最短路
(1)给定邻接矩阵的Bellman-ford
代码
class Solution:
def bellmanford(self, n: int, w: List[List[int]]) -> List[int]:
dp = [[0] * n for _ in range(n)]
for k in range(n):
for j in range(n):
for i in range(n):
dp[k][j] = min(dp[k][j], dp[k - 1][i] + w[i][j])(2)给定edges的Bellman-ford,edges[i] = [i, j, wij]表示从i出发到j的边权重为wij
代码
class Solution:
def bellmanford(self, n: int, edges: List[List[int]]) -> List[int]:
dp = [[0] * n for _ in range(n)]
for k in range(n):
for i, j, wij in edges:
dp[k][j] = min(dp[k][j], dp[k - 1][i] + wij)2. Dij:单源最短路
核心思想：贪心 + 堆，贪心取距离源点最近的节点加入集合
(1)每次取出距离源点最近的点u, 将u加入集合vis，使用堆取最短路。首次距离源点最近的点是源点本身
(2)更新vis外围一圈的节点到源点的距离（所以用BFS）, 因为只有u节点加入了vis, 所以到源点的距离发生变化的点v一定与u相连
(3)如果某个点v距离源点的距离通过u变小了，就将它加入堆中
(4)重复23直到堆为空，注意堆内可能有多个相同节点，我们只取第一次遍历到的节点，因为用堆取出，所以它一定是最短路
代码
class Solution:
def dij(self, n: int, edges: List[List[int]]) -> List[int]:
# 根据edges构建邻接表g，并且记录路径长度l
g = collections.defaultdict(list)
for u, v, l in edges:
g[u].append((v, l))
g[v].append((u, l))
# 假设源点为0点
# dij的前期准备，dis表示0到其它点的距离，0点先进入堆q，并构造集合vis表示已经找到距离0的最短路的点集合
q = [(0, 0)]
vis = set()
dis = [inf] * n
dis[0] = 0
# dij最短路模板
while q:
# 每次取出距离0点最近的点u, 将u加入集合vis
d, u = heapq.heappop(q)
# 剪枝：如果某次d大于之前的0到u的距离，那么点u一定已经被遍历过了
if d > dis[u]: continue
vis.add(u)
# 更新剩余节点到0的距离, 因为新加入了u, 所以发生变化的距离只有u的邻接点v
for v, duv in g[u]:
# 如果存在某个点到0的距离通过u变小了，就将它加入堆中
if (v not in vis) and dis[u] + duv < dis[v]:
dis[v] = dis[u] + duv
heapq.heappush(q, (dis[v], v))3. Floyd:多源最短路
核心思想：记忆化搜索/动态规划，考虑ij中间最大编号的节点k是否要选
对于任意两点i和j之间的最短路，考虑ij路径的中间节点（不包含ij）编号最大的节点k，根据背包问题的思想，我们在选择k和不选择k的方案里选择路径长度最小的作为结果。
如果选择k，则ij之间的路径=i到k的路径 + k到j的路径，而且路径之间的中间结点的编号<=k - 1；
如果不选择k，则ij之间的路径等价于ij之间中间节点编号<=k - 1的路径
(1)记忆化搜索
dfs(k, i, j)表示ij路径的中间节点（不包含ij）编号最大为k的最短路
选择k：dfs(k - 1, i, k) + dfs(k - 1, k, j)
不选择k：dfs(k - 1, i, j)
递归边界：k = -1，ij中间编号最大为-1，即ij中间没有任何中间节点，此时ij之间的最短路就是两者中间的路径长度w[i][j]
递归入口：记忆化搜索的递归方向是k从大到小，因此递归的入口是dfs(n - 1, i, j)，取最大编号n - 1
代码
class Solution:
def floyd(self, n: int, w: List[List[int]]) -> List[int]:
@cache
def dfs(k, i, j):
if k == -1: return w[i][j]
return min(dfs(k - 1, i, j), dfs(k - 1, i, k) + dfs(k - 1, k, j))
for i in range(n):
for j in range(n):
dis = dfs(n - 1, i, j)(2)动态规划
将记忆化搜索的函数入口变量全部转为dp的状态即可，注意记忆化搜索的k可以为-1，但dp的k是数组的索引，因此最小为0，可以将dp的k整体+1，避免数组越界。
dp[k + 1][i][j]表示ij路径的中间节点（不包含ij）编号最大为k的最短路
初始化：参考递归边界，k = 0时是初始状态，使用w数组直接初始化dp，dp[0][i][j] = w[i][j] = dfs(-1, i, j)
代码
class Solution:
def floyd(self, n: int, w: List[List[int]]) -> List[int]:
dp = [[[0] * n for _ in range(n)] for _ in range(n + 1)]
dp[0] = w
for k in range(n):
for i in range(n):
for j in range(n):
dp[k + 1][i][j] = min(dp[k][i][j], dp[k][i][k] + dp[k][k][j])(3)动态规划 + 空间优化
回想起0-1背包和完全背包，我们可以优化第0个维度的空间。优化时需要考虑更新时需要用旧值(01背包j倒序)还是更新后的值(完全背包j正序)。但Floyd的dp[i][k]和dp[k][j]无法判断i、k、j谁大谁小。但这里有一个更好的性质：
dp[k + 1][i][k] = dp[k][i][k]
dp[k + 1][k][j] = dp[k][k][j]
这是因为dp[k + 1][i][k]表示ik路径的中间节点（不包含ik）编号最大为k的最短路，但是k已经是端点，所以ik路径的中间节点编号必然<=k - 1，因此等于dp[k][i][k]。所以，可以直接拿掉第一个维度，而且ij的遍历顺序不需要更改。
代码
class Solution:
def floyd(self, n: int, w: List[List[int]]) -> List[int]:
dp = [w[i].copy() for i in range(n)]
for k in range(n):
for i in range(n):
for j in range(n):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])