什么是单源全源最短路?
单源全源最短路是一个在图论中的概念。单源最短路指的是在一个图中，从一个特定的顶点（称为源点）到其他所有顶点的最短路径。而全源最短路则是对于图中的每一个顶点都作为源点，分别计算到其他所有顶点的最短路径。这一概念常用于优化路径规划、网络通信等领域，以找到最优的连接方式或传输路径，从而提高效率和降低成本。

单源最短路: dijkstra

单源:start 到 end, 能到达返回最短路距离, 不能则返回 -1

朴素dijkstra

适用于稠密图(边多, 边数大于n方), 用邻接矩阵建图

g = [[inf] * n for _ in range(n)]
for i in range(n):
    g[i][i] = 0
for x, y, w in edges:
    g[x][y] = g[y][x] = w  
dis = [inf] * n  # 从 start 出发，到各个点的最短路，如果不存在则为无穷大
dis[start] = 0
vis = [False] * n
while True:  # 至多循环 n 次
    x = -1
    for i, (b, d) in enumerate(zip(vis, dis)):
        if not b and (x < 0 or d < dis[x]):
            x = i
    if x < 0 or dis[x] == inf:  # 所有从 start 能到达的点都被更新了
        return -1  # 无法到达终点
    if x == end:  # 找到终点，提前退出
        return dis[x]
    vis[x] = True  # 标记，在后续的循环中无需反复更新 x 到其余点的最短路长度
    for y, w in enumerate(g[x]):
        if dis[x] + w < dis[y]:
            dis[y] = dis[x] + w  # 更新最短路长度`

堆优化 dijkstra

适用于稀疏图, 用邻接表建图

g = [[] for _ in range(n)]  # 邻接表
for x, y, w in edges:
    g[x].append((y, w))
    g[y].append((x, w))
dis = [inf] * n  # dis[i] 表示从起点 start 出发，到节点 i 的最短路长度
dis[start] = 0
h = [(0, start)]
while h:
    d, x = heappop(h)
    if x == end:  # 计算出从起点到终点的最短路长度
        return d
    if d > dis[x]:  # x 之前出堆过，无需更新邻居的最短路
        continue
    for y, w in g[x]:
        if d + w < dis[y]:
            dis[y] = d + w  # 更新最短路长度
            heappush(h, (dis[y], y))
return -1  # 无法到达终点

全源最短路: floyd

最易写的最短路, 缺点是时间复杂度高, O(n^3), 本质是动态规划求最短路

g = [[inf] * n for _ in range(n)]
for i in range(n):
    g[i][i] = 0
for x, y, w in roads:
    g[x][y] = min(g[x][y], w)
    g[y][x] = min(g[y][x], w)
for k in range(n):
    for i in range(n):
        if f[i][k] == inf: continue
        for j in range(n):
            f[i][j] = min(f[i][j], f[i][k] + f[k][j])

题单:
https://leetcode.cn/problems/design-graph-with-shortest-path-calculator/description/ (模板题)