功能说明
Floyd-Warshall 适合节点数不多的稠密图，一次计算就能得到所有点对之间的最短距离。算法依次把每个节点当作中转点，尝试用起点到中转点再到终点的距离更新起点到终点的距离。只要图中没有负权环，结果就是正确的；存在负权边也可以处理，这是它相对于 Dijkstra 的优势。
本例同时维护距离矩阵和下一跳矩阵。距离矩阵初始时对角线为零，直接边为权重，其余为无穷。更新距离成功时，把下一跳改为起点到中转点的下一跳，从而在结束后按矩阵逐跳还原完整路径。
关键代码
floyd_warshall 先收集排序后的节点，建立二维字典，避免依赖节点命名。无穷用 float 的 inf 表示，对角线初始化为零。读入边时写入距离和下一跳。三重循环外层是中转点，内层是起点和终点；若起点到中转点不可达就跳过，减少无效加法。候选距离更小时同时更新距离和下一跳。build_path 从起点开始，按下一跳前进直到终点；起点等于终点时直接返回单节点路径。
使用注意
时间复杂度是节点数三次方，空间是平方，节点数上千时会明显变慢，应改用逐源 Dijkstra 或 Johnson 算法。距离用浮点表示可能产生舍入误差，金额或精确权值应使用整数。该实现没有检测负权环；若某节点到自身的距离被更新为负数，说明存在负权环。图字典未列出的节点不会出现，隐式节点需要先补齐。路径还原前应确认下一跳矩阵已正确初始化。
验证方式
运行脚本，A 到 C 的最短距离为五，路径为 A、B、C；D 到 C 经过 A 与 B，距离为七；C 到自身距离为零，路径只含 C。修改某条边权后重跑，距离和路径应同步变化。可加入一个负权边但不构成环，验证算法仍能给出更短路径。
代码示例
INF = float("inf")
def floyd_warshall(
graph: dict[str, dict[str, float]]
) -> tuple[dict[str, dict[str, float]], dict[str, dict[str, str | None]]]:
nodes = sorted(graph)
dist = {source: {target: INF for target in nodes} for source in nodes}
nxt: dict[str, dict[str, str | None]] = {
source: {target: None for target in nodes} for source in nodes
}
for node in nodes:
dist[node][node] = 0.0
for source, edges in graph.items():
for target, weight in edges.items():
dist[source][target] = weight
nxt[source][target] = target
for middle in nodes:
for source in nodes:
if dist[source][middle] == INF:
continue
for target in nodes:
candidate = dist[source][middle] + dist[middle][target]
if candidate < dist[source][target]:
dist[source][target] = candidate
nxt[source][target] = nxt[source][middle]
return dist, nxt
def build_path(
nxt: dict[str, dict[str, str | None]], source: str, target: str
) -> list[str] | None:
if source == target:
return [source]
if nxt[source][target] is None:
return None
route = [source]
while source != target:
step = nxt[source][target]
if step is None:
return None
source = step
route.append(source)
return route
if __name__ == "__main__":
graph = {
"A": {"B": 3.0, "D": 7.0},
"B": {"A": 8.0, "C": 2.0},
"C": {"A": 5.0, "D": 1.0},
"D": {"A": 2.0},
}
dist, nxt = floyd_warshall(graph)
print("A to C:", dist["A"]["C"], build_path(nxt, "A", "C"))
print("D to C:", dist["D"]["C"], build_path(nxt, "D", "C"))
print("C to C:", dist["C"]["C"], build_path(nxt, "C", "C"))