白沙黎族自治县网站建设_网站建设公司_原型设计_seo优化

floyd算法求最小距离代码

def floyd(graph): n = len(graph) dist = [[0]*n for _ in range(n)] # 初始化距离矩阵 for i in range(n): for j in range(n): dist[i][j] = graph[i][j] # 三重循环暴力更新 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] return dist

这个初始化部分有个小细节容易被新手忽略——为什么要单独搞个dist矩阵而不是直接修改原图？想象一下你在更新A到C的距离时，如果直接改原矩阵，后面的B到D的计算可能就用了被污染的数据。这种"数据污染防护"机制挺重要。

中间那个三重循环看起来吓人，其实可以拆解来看。假设现在要计算北京到广州的最短距离，k=武汉这个中间站。算法会先问："北京->武汉->广州 比 北京直达广州 近吗？"如果近就更新。接着k换成郑州、长沙...直到所有可能的中转站都检查一遍。

来看看具体更新逻辑：

if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j]

这行代码藏着动态规划的精髓——最优子结构。就像拼乐高，大问题（i到j）的解建立在更小子问题（i到k和k到j）的最优解之上。不过要注意这里的k遍历顺序，最外层必须是中间节点，这个顺序如果搞反了算法就废了。

实际应用时可以加点路径追踪功能。我们可以在初始化时创建个path矩阵：

path = [[-1]*n for _ in range(n)] if dist[i][j] > dist[i][k] + dist[k][j]: dist[i][j] = dist[i][k] + dist[k][j] path[i][j] = k # 记录关键转折点

这样要查具体路径时，就可以用递归把路径拆成i->k和k->j两段，直到找到-1标识的直达路线。

虽然时间复杂度O(n³)看着吓人，但在实际项目中处理几百个节点的图还是能hold住的。不过要注意输入图的表示方式，如果节点太多建议换稀疏矩阵存储。对了，算法处理负权边时要当心，万一图里有负权环就完犊子了，这时候得用其他法子。