请再仔细看看这段的代码的问题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
时间: 2023-12-15 14:03:13 浏览: 87
这段代码存在两个问题:
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
```
相关问题
请给出这段代码的完整修改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)~=0 && 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 pathNodes ~= s pathNodes = path(pathNodes); path = [pathNodes, path]; end path = [s, path]; end end
function [dist,path] = dijkstra(D,s,t)
% D: 邻接矩阵,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; % 起点到自己的距离为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) ~= 0 && 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 pathNodes ~= s
pathNodes = path(pathNodes);
path = [pathNodes, path];
end
path = [s, path];
end
end
找到这段代码的问题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), path(pathNodes)]; end path = [s, pathNodes, t]; end end
这段代码存在一个问题:在构建路径的时候,当 path(t) 不等于 0 时,pathNodes 的初始化值应该为 t,而不是 [t]。因为 pathNodes 后面会被赋值为 path(pathNodes),如果 path(t) 不等于 0,path(t) 所在的位置会被赋值为 s,导致 pathNodes 的值为 [t, s],最终得到的路径会包含重复的节点。
阅读全文