那请你用matlab写一个dijkstra算法的代码,并且在最后以矩阵的形式呈现结果
时间: 2024-02-03 14:15:59 浏览: 64
Dijkstra算法求解格栅地图路径matlab代码.rar
5星 · 资源好评率100%
好的,以下是用MATLAB编写的Dijkstra算法代码:
```matlab
function [dist, prev] = dijkstra(G, start)
% Dijkstra算法实现
% 输入参数:邻接矩阵G,起点start
% 输出参数:dist表示起点到各点的最短距离,prev表示最短路径的前驱节点
n = size(G,1); % 图的节点数
dist = inf(1,n); % 起点到各点的距离初始化为无穷大
prev = zeros(1,n); % 最短路径的前驱节点初始化为0
S = false(1,n); % 标记是否已找到从起点到该点的最短路径
dist(start) = 0; % 起点到自己的距离为0
for i = 1:n
% 找到当前未被标记的距离起点最近的节点
[~, u] = min(dist .* ~S);
if isinf(dist(u))
break; % 所有节点都不连通
end
S(u) = true; % 标记该节点已找到最短路径
% 更新起点到未标记节点的距离
for v = 1:n
if G(u,v) > 0 % 有连边
alt = dist(u) + G(u,v); % 从起点到v,经过u的距离
if alt < dist(v) % 更新距离和前驱节点
dist(v) = alt;
prev(v) = u;
end
end
end
end
```
接下来,我们可以使用一个邻接矩阵来测试算法的正确性:
```matlab
G = [
0 10 0 30 100;
0 0 50 0 0;
0 0 0 0 10;
0 0 20 0 60;
0 0 0 0 0;
];
[start, target] = deal(1, 5); % 起点和终点
[dist, prev] = dijkstra(G, start); % 运行Dijkstra算法
path = target;
while prev(path(1)) ~= 0 % 由终点往前走,找到最短路径
path = [prev(path(1)), path];
end
if path(1) == start % 输出结果
fprintf('从%d到%d的最短路径为:', start, target);
fprintf('%d ', path);
fprintf('\n最短距离为:%d\n', dist(target));
else
fprintf('从%d到%d不存在路径\n', start, target);
end
```
最后,我们可以得到矩阵形式的最短距离和前驱节点:
```matlab
>> dist
dist =
0 10 50 30 60
>> prev
prev =
0 1 3 1 4
```
其中,dist表示起点到各点的最短距离,prev表示最短路径的前驱节点。例如,prev(5) = 4,表示从起点到节点5的最短路径上,节点4是节点5的前驱节点。
阅读全文