在图论中，寻找两点之间的最短路径是一个非常常见的问题。Dijkstra算法作为解决这类问题的经典方法之一，被广泛应用于网络路由、交通规划、资源分配等多个领域。本文将介绍如何使用MATLAB对Dijkstra算法进行实现，并通过具体示例展示其运行过程与结果。
一、Dijkstra算法简介
Dijkstra算法是由荷兰计算机科学家艾兹赫尔·戴克斯特拉（Edsger W. Dijkstra）于1956年提出的一种贪心算法，用于求解单源最短路径问题。该算法适用于边权为非负数的有向图或无向图。
其基本思想是：从起点出发，每次选择当前距离最小的节点进行扩展，逐步更新其他节点到起点的最短距离，直到所有节点都被处理完毕或目标节点被找到。
二、算法步骤
1. 初始化：设置一个距离数组dist，其中dist[i]表示从起点到节点i的最短距离。初始时，起点的距离为0，其余节点设为无穷大。
2. 维护未访问节点集合：记录所有尚未确定最短路径的节点。
3. 循环选择当前距离最小的节点u，并将其标记为已访问。
4. 遍历u的所有邻接节点v，若通过u到达v的距离比当前记录的更小，则更新dist[v]。
5. 重复步骤3和4，直到所有节点都被访问或目标节点被处理。
三、MATLAB实现
下面是一个基于MATLAB的Dijkstra算法实现代码示例：
```matlab
function [dist, path] = dijkstra(graph, start)
% graph: 邻接矩阵，graph(i,j) 表示节点i到j的边权
% start: 起始节点索引
n = size(graph, 1);
dist = inf(1, n);% 初始化距离为无穷大
dist(start) = 0; % 起点距离为0
visited = false(1, n); % 标记是否已访问
prev = zeros(1, n);% 记录前驱节点
for _ = 1:n
% 找到当前距离最小的未访问节点
[~, u] = min(dist . ~visited);
visited(u) = true;
% 遍历u的所有邻接节点
for v = 1:n
if ~visited(v) && graph(u, v) > 0
if dist(v) > dist(u) + graph(u, v)
dist(v) = dist(u) + graph(u, v);
prev(v) = u;
end
end
end
end
% 构建路径
path = [];
current = find(dist == inf, 1);
if ~isempty(current)
disp('存在不可达节点');
else
current = n;% 假设要找终点n的路径
while current ~= start
path = [current, path];
current = prev(current);
end
path = [start, path];
end
end
```
四、示例测试
假设我们有一个简单的图，邻接矩阵如下：
```
graph = [
0 4 0 0 0;
4 0 8 0 0;
0 8 0 7 2;
0 0 7 0 9;
0 0 2 9 0;
];
```
调用函数：
```matlab
[start, end] = deal(1, 5);
[dist, path] = dijkstra(graph, start);
disp(['最短路径长度：', num2str(dist(end))]);
disp(['最短路径：', num2str(path)]);
```
输出可能为：
```
最短路径长度：14
最短路径：135
```
五、总结
Dijkstra算法是一种高效且实用的最短路径求解方法，尤其适合处理边权为非负值的图结构。通过MATLAB实现该算法，可以快速验证算法逻辑，并用于实际工程中的路径规划与优化问题。希望本文能帮助读者更好地理解Dijkstra算法的原理及其在MATLAB中的应用。
