Floyd最短路径算法代码

Floyd-Warshall算法是一种用于计算所有节点对之间最短路径的经典图算法。它适用于加权有向或无向图，即使图中存在负权重边。以下是使用Python编写的Floyd-Warshall算法的简单版本：

def floyd_warshall(graph):
    n = len(graph) # 获取节点数
    dist = graph.copy() # 复制原图作为距离矩阵
    for k in range(n): # 对每个中间节点进行遍历
        for i in range(n):
            for j in range(n):
                # 如果通过中间节点k的路径比直接相连更短，则更新路径
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

# 示例图（邻接矩阵表示）
graph = [
    [0, 4, 0, 0],
    [4, 0, 8, 0],
    [0, 8, 0, 11],
    [0, 0, 11, 0]
]

floyd_warshall_result = floyd_warshall(graph)
print("最小路径矩阵: ")
for row in floyd_warshall_result:
    print(row)

相关问题

Floyd最短路径算法c++

Floyd-Warshall 算法是一种用于计算图中所有节点对之间最短路径的动态规划方法。在 C++ 中实现这个算法，通常用于解决求解有向或无向图中任意两点间的最短路径问题。以下是算法的主要步骤和一个简单的 C++ 示例：

1. 初始化距离矩阵：对于图中的每条边 (u, v)，如果起点 u 可以通过这条边直接到达终点 v，那么初始的距离矩阵中，d[u][v] 就是这条边的权重；否则，距离为无穷大。

2. 动态更新：对所有的中间节点 k 进行循环（从 0 到 n-1，n 为节点数），检查是否存在这样的情况：d[i][j] > d[i][k] + d[k][j]。如果存在，说明通过 k 中间节点的路径更短，就更新 d[i][j] 的值。

3. 重复步骤2，直到没有更多的路径可以更新，此时得到的 d[][] 中的值就是最终的最短路径。

以下是一个简化的 C++ 代码实现：

#include <vector>
#include <climits>

// 假设 weights 为邻接矩阵，表示图的权重
void floydWarshall(std::vector<std::vector<int>>& weights) {
    int n = weights.size();
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (weights[i][j] > weights[i][k] + weights[k][j]) {
                    weights[i][j] = weights[i][k] + weights[k][j];
                }
            }
        }
    }
}

// 使用示例
std::vector<std::vector<int>> graph = {{0, 1, INT_MAX}, {INT_MAX, 0, 4}, {2, INT_MAX, 0}}; // 用 INT_MAX 表示无穷远
floydWarshall(graph);

floyd最短路径算法 matlab

Floyd最短路径算法是一种经典的算法，用于求解加权图中两个节点之间的最短路径。该算法基于动态规划的思想，通过不断更新路径中的节点，逐步求得最短路径。下面是Floyd算法的MATLAB实现代码 = Floyd(W, start, stop)
% start为指定起始结点，stop为指定终止结点
D = W; % 最短距离矩阵赋初值
n = length(D); % n为结点个数
P = zeros(n,n); % 路由矩阵赋初值

for i = 1:n
for j = 1:n
P(i,j) = j;
end
end

for k = 1:n
for i = 1:n
for j = 1:n
if D(i,k) + D(k,j) < D(i,j) % 核心代码
D(i,j) = D(i,k) + D(k,j);
P(i,j) = P(i,k);
end
end
end
end

if nargin ~= 3
errordlg('参数个数输入有误！', 'Warning!')
else
dis = D(start, stop); % 指定两结点间的最短距离
m(1) = start;
i = 1;
while P(m(i),stop) ~= stop
k = i + 1;
m(k) = P(m(i),stop);
i = i + 1;
end
m(i + 1) = stop;
path = m; % 指定两结点之间的最短路径
end
end

该代码实现了Floyd算法，并输出了最短距离矩阵和路径矩阵，以及指定两个节点间的最短距离和路径。你可以根据需求调用该函数并传入相应的参数，即可得到所需的结果。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
-  *1* *2* *3* [Floyd算法及其MATLAB实现](https://blog.csdn.net/qq_42916979/article/details/104128709)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]