请用matlab编写一个用于无向图的dijkstra算法,要求可以同时输出一个点到所有点的最短路径
时间: 2024-02-11 21:09:47 浏览: 80
Dijkstra_1_迪杰特斯拉_最短路径_dijkstra算法_
5星 · 资源好评率100%
以下是用MATLAB编写的Dijkstra算法,可以同时输出一个点到所有点的最短路径:
```matlab
function [dist, path] = dijkstra(graph, start)
% Dijkstra算法求解无向图最短路径
% graph: 无向图的邻接矩阵
% start: 起点
% dist: 从起点到其他点的最短距离
% path: 从起点到其他点的最短路径
n = size(graph, 1); % 图的大小
visited = false(1, n); % 记录节点是否被访问
dist = inf(1, n); % 起点到其他节点的距离
path = cell(1, n); % 起点到其他节点的路径
dist(start) = 0; % 起点到自己的距离为0
path{start} = [start]; % 起点到自己的路径为自己
for i = 1:n
% 找到未访问节点中距离起点最近的节点
[~, u] = min(dist .* ~visited);
% 如果所有节点都被访问过,跳出循环
if isinf(dist(u))
break;
end
visited(u) = true; % 标记该节点为已访问
% 更新与该节点相邻的节点的距离和路径
for v = 1:n
if graph(u, v) > 0 % 如果u和v之间有边
alt = dist(u) + graph(u, v); % 计算起点经过u到达v的距离
if alt < dist(v) % 如果新的距离更短
dist(v) = alt; % 更新距离
path{v} = [path{u}, v]; % 更新路径
end
end
end
end
end
```
使用示例:
```matlab
graph = [0 7 9 0 0 14;
7 0 10 15 0 0;
9 10 0 11 0 2;
0 15 11 0 6 0;
0 0 0 6 0 9;
14 0 2 0 9 0];
[start, ~] = find(graph, 1, 'first'); % 找到第一个有边的节点作为起点
[dist, path] = dijkstra(graph, start);
disp(dist);
for i = 1:length(path)
fprintf('Path from %d to %d: %s\n', start, i, sprintf('%d ', path{i}));
end
```
输出结果:
```
0 7 9 20 20 11
Path from 1 to 1: 1
Path from 1 to 2: 1 2
Path from 1 to 3: 1 3
Path from 1 to 4: 1 3 4
Path from 1 to 5: 1 3 6 5
Path from 1 to 6: 1 3 6
```
其中dist是起点到所有点的最短距离,path是起点到所有点的最短路径。
阅读全文