floyd算法实现思路及实例代码

Floyd算法，又称Floyd-Warshall算法，是一种计算图中所有最短路径的动态规划算法。它可以处理包括负权边（但不能处理负权环）的加权图。以下是Floyd算法的基本实现思路及一个简单的Python实例代码。

### Floyd算法实现思路

1. **初始化**：首先，将图的邻接矩阵初始化，如果顶点i到顶点j有边，则邻接矩阵的`dist[i][j]`为边的权重；如果顶点i到顶点j无边，则`dist[i][j]`为无穷大（在程序中通常用一个很大的数表示，如`float('inf')`）。对于每个顶点v，`dist[v][v]`为0。

2. **三层循环**：

- 外层循环遍历所有顶点k，作为中间顶点。

- 中间循环遍历所有起点i。

- 内层循环遍历所有终点j。

- 如果从i到k的距离加上从k到j的距离小于直接从i到j的距离，则更新`dist[i][j]`为更小的值。

3. **结果**：经过上述三层循环后，`dist[i][j]`中存储的就是i到j的最短路径长度。

### Python实例代码

import sys

# 初始化图的邻接矩阵
def init_graph(n):
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    return dist

# Floyd算法实现
def floyd_warshall(dist, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

# 示例图的邻接矩阵
# 注意：这里假设图是无向的，且边的权重为1（除了直接相连的边外，其他边的权重默认为无穷大）
n = 4  # 顶点数量
edges = [(0, 1), (1, 2), (2, 3), (3, 0), (1, 3)]  # 示例边

dist = init_graph(n)
for u, v in edges:
    dist[u][v] = 1
    dist[v][u] = 1  # 因为是无向图

floyd_warshall(dist, n)

# 输出结果
for row in dist:
    print(row)

注意：上述代码中的`edges`列表仅用于初始化示例图的邻接矩阵，其中`(u, v)`表示顶点u和顶点v之间有边相连，且边的权重为1。在实际应用中，你可能需要根据具体的图结构和边的权重来初始化邻接矩阵。