Dijkstra算法matlab实现
时间: 2023-10-16 20:32:17 浏览: 37
以下是Dijkstra算法的Matlab实现:
```matlab
function [dist, path] = dijkstra(adj_mat, source, dest)
% Dijkstra算法计算最短路径
% adj_mat: 邻接矩阵
% source: 起点
% dest: 终点
% dist: 最短距离
% path: 最短路径
n = size(adj_mat, 1);
dist = Inf(1, n); % 初始距离为无穷大
dist(source) = 0; % 起点到起点的距离为0
path = zeros(1, n); % 记录路径
visited = zeros(1, n); % 标记是否已访问
for i = 1:n
[~, u] = min(dist + visited * Inf); % 选择最小距离的节点
if u == dest || isinf(dist(u)) % 如果已经到达终点或无法到达任何节点,则退出
break;
end
visited(u) = 1; % 标记为已访问
for v = 1:n
if adj_mat(u, v) ~= 0 && ~visited(v) % 如果两个节点有连接,并且未访问
alt = dist(u) + adj_mat(u, v); % 计算新的距离
if alt < dist(v) % 如果新的距离更短
dist(v) = alt; % 更新距离
path(v) = u; % 更新路径
end
end
end
end
% 构建路径
if isinf(dist(dest)) % 如果无法到达终点
path = [];
else
p = dest;
while p ~= source
path = [p path];
p = path(1);
end
path = [source path];
end
end
```
其中,邻接矩阵`adj_mat`表示节点之间的距离,若两个节点不连通则距离为0;起点为`source`,终点为`dest`。算法返回最短距离`dist`和最短路径`path`。