请再仔细看看这段的代码的问题function [dist,path] = dijkstra(D,s,t) % G：邻接矩阵，s：起点，t：终点 % dist：s到所有点的最短距离，path：s到t的最短路径 n = size(D, 1); dist = inf(1,n); % 到各点的距离 path = zeros(1,n); % 到各点的路径 S = false(1,n); % 是否已经找到最短路径 dist(s) = 0; for i = 1 : n minDist = inf; u = -1; % 找到当前未找到最短路径的点中距离最近的点 for j = 1 : n if ~S(j) && dist(j) < minDist minDist = dist(j); u = j; end end if u == -1 || u == t break; end % 标记已经找到最短路径 S(u) = true; % 更新其它点到起点的距离 for j = 1 : n if ~S(j) && D(u,j)~=inf && dist(j) > dist(u) + D(u,j) dist(j) = dist(u) + D(u,j); path(j) = u; end end end % 构建路径 if path(t) == 0 path = []; else pathNodes = t; while path(pathNodes) ~= s pathNodes = path(pathNodes); end path = [s, pathNodes, t]; end end

这段代码存在两个问题：

1. 在构建路径时，应该先将终点 t 加入到 path 中，然后再从终点开始沿着最短路径向前找到起点 s，将每个节点都加入到 path 中，最后再将 path 反转过来。修改后的代码如下：

% 构建路径
if path(t) == 0
    path = [];
else
    pathNodes = t;
    while pathNodes ~= s
        pathNodes = path(pathNodes);
        path = [pathNodes, path];
    end
    path = [s, path];
end

2. 在找到最短路径的点时，应该判断 D(u,j) 是否等于 0，而不是 D(u,j) 是否等于 inf。因为 D(u,j) 等于 0 表示 u 和 j 相邻，不存在边，距离为无穷大；而 D(u,j) 等于 inf 表示 u 和 j 不相邻，不存在边，距离为无穷大。修改后的代码如下：

for j = 1 : n
    if ~S(j) && D(u,j)~=0 && dist(j) > dist(u) + D(u,j)
        dist(j) = dist(u) + D(u,j);
        path(j) = u;
    end
end