Matlab矩阵中第一、第二最短路径完整输出问题排查

问题核心 #

你的代码无法输出完整路径，且次短路径逻辑失效，根源在于邻接矩阵处理完全错误、Dijkstra节点选择逻辑错误、路径回溯及边移除逻辑漏洞。

关键错误点 #

1. 邻接矩阵篡改：原代码中matrix = matrix + matrix'会加倍无向图的边权，后续matrix(matrix == inf) = 0; matrix(matrix > 0) = inf;直接把所有有效边置为inf（即删除所有边），导致Dijkstra算法无法找到前驱节点，prev数组全为0，只能输出终点。
2. 节点选择逻辑错误：每次选未标记节点时，忽略了min(d(~S))的结果，直接选第一个未标记节点，根本不符合Dijkstra算法“选距离最小节点”的核心逻辑。
3. 路径回溯问题：第一路径回溯后未反转，输出顺序是终点到起点；第二路径回溯条件错误，无法正确追溯到起点。
4. 边移除不彻底：仅移除单向边，无向图需双向移除第一路径的所有边。

修复后的完整代码 #

% 示例邻接矩阵（可替换为Excel读取的矩阵，如matrix = readmatrix('your_file.xlsx')）
matrix = [0  3  6  8  2  inf  inf  inf  inf  inf;
          3  0  5  7  9   1  inf  inf  inf  inf;
          6  5  0  5  8   10  2  inf  inf  inf;
          8  7  5  0  4   9   14  3  inf  inf;
          2  9  8  4  0   5   12  15  4  inf;
          inf  1  10  9  5  0   10  20  25  5;
          inf  inf  2  14  12  10  0   12  30  35;
          inf  inf  inf  3  15  20  12  0   25  40;
          inf  inf  inf  inf  4  25  30  25  0   45;
          inf  inf  inf  inf  inf  5  35  40  45  0];

% 起点、终点设置
start = 1;
ending = 10;

% 初始化变量
n = size(matrix, 1); % 节点数
d = inf(1, n); % 距离数组
d(start) = 0; % 起点距离为0
prev = zeros(1, n); % 前驱节点数组
S = false(1, n); % 已标记节点集合
S(start) = true;

% 处理对角线0（节点到自身的距离设为inf）
for i = 1:n
    if matrix(i,i) == 0
        matrix(i,i) = inf;
    end
end

% ---------------------- 第一最短路径计算 ----------------------
while ~S(ending)
    % 选择未标记节点中距离最小的节点v
    [min_dist, idx] = min(d(~S));
    v = find(~S, idx);
    S(v) = true; % 标记该节点
    
    % 更新邻接节点的距离和前驱
    for u = find(matrix(v,:) ~= inf)
        if d(v) + matrix(v,u) < d(u)
            d(u) = d(v) + matrix(v,u);
            prev(u) = v;
        end
    end
end

% 回溯并整理第一路径
path = [ending];
while prev(path(end)) ~= 0
    path = [path, prev(path(end))];
end
path = fliplr(path); % 反转得到起点到终点的顺序

% 输出第一路径（格式：1-2-6-10）
fprintf('First Shortest Path: ');
for i = 1:length(path)
    if i == length(path)
        fprintf('%d\n', path(i));
    else
        fprintf('%d-', path(i));
    end
end

% ---------------------- 第二最短路径计算 ----------------------
% 移除第一路径的所有双向边
for i = 2:length(path)
    u = path(i-1);
    v = path(i);
    matrix(u, v) = inf;
    matrix(v, u) = inf;
end

% 重新初始化Dijkstra变量
d = inf(1, n);
d(start) = 0;
prev = zeros(1, n);
S = false(1, n);
S(start) = true;

while ~S(ending)
    [min_dist, idx] = min(d(~S));
    v = find(~S, idx);
    S(v) = true;
    
    for u = find(matrix(v,:) ~= inf)
        if d(v) + matrix(v,u) < d(u)
            d(u) = d(v) + matrix(v,u);
            prev(u) = v;
        end
    end
end

% 回溯并整理第二路径
path2 = [ending];
while prev(path2(end)) ~= 0
    path2 = [path2, prev(path2(end))];
end
path2 = fliplr(path2);

% 输出第二路径
fprintf('Second Shortest Path: ');
for i = 1:length(path2)
    if i == length(path2)
        fprintf('%d\n', path2(i));
    else
        fprintf('%d-', path2(i));
    end
end

修复说明 #

1. 删除错误的邻接矩阵处理代码：保留原邻接矩阵的有效性，仅处理对角线的自环距离。
2. 修正Dijkstra节点选择逻辑：正确选取未标记节点中距离最小的节点，符合算法核心逻辑。
3. 路径回溯后反转：确保输出顺序为起点到终点，且格式符合要求（用-连接）。
4. 双向移除路径边：针对无向图，彻底删除第一路径的所有边，保证次短路径不重复使用原路径。
5. 支持Excel矩阵读取：替换matrix的赋值为matrix = readmatrix('your_excel_file.xlsx')即可读取外部矩阵。

内容的提问来源于stack exchange，提问作者Mr Sir