Bellman-Ford 算法代码matlab

下面是 Bellman-Ford 算法的 Matlab 代码实现：

function [dist, path] = bellmanFord(G, s)
% G: 图的邻接矩阵
% s: 起点

n = size(G, 1); % 图中节点数
dist = inf(1, n); % 初始化起点到各点的最短距离为无穷大
dist(s) = 0; % 起点到自己的距离为0
path = zeros(1, n); % 初始化路径数组
path(s) = s; % 起点到自己的路径为自己

% 进行n-1轮松弛操作
for i = 1:n-1
    for u = 1:n
        for v = 1:n
            if G(u, v) ~= 0 % 边存在
                if dist(u) + G(u, v) < dist(v)
                    % 更新最短距离和路径
                    dist(v) = dist(u) + G(u, v);
                    path(v) = u;
                end
            end
        end
    end
end

% 检查是否存在负权回路
for u = 1:n
    for v = 1:n
        if G(u, v) ~= 0 % 边存在
            if dist(u) + G(u, v) < dist(v)
                error('存在负权回路');
            end
        end
    end
end
end

其中，`G` 为图的邻接矩阵，`s` 为起点。函数返回值 `dist` 为起点到各点的最短距离，`path` 为最短路径中每个节点的前驱节点。如果图中存在负权回路，则会抛出异常。