dijkstra算法的MATLAB实现
时间: 2024-05-30 16:06:34 浏览: 10
Dijkstra算法是一种经典的最短路径搜索算法,主要用于解决单源最短路径问题。MATLAB是一种强大的数学软件,可以用于实现Dijkstra算法。
以下是Dijkstra算法在MATLAB中的简单实现:
```matlab
function [dist, path] = dijkstra(graph, startNode, endNode)
% graph: 邻接矩阵表示的图
% startNode: 起点编号
% endNode: 终点编号
% dist: 起点到每个节点的最短距离
% path: 起点到终点的最短路径
n = size(graph, 1);
dist = inf(1, n); % 初始化距离为无穷大
dist(startNode) = 0; % 起点到自身距离为0
visited = false(1, n); % 初始化所有节点未被访问过
for i = 1:n
[~, u] = min(dist .* ~visited); % 找到未访问节点中距离最小的节点
visited(u) = true; % 标记该节点为已访问
for v = 1:n
if graph(u, v) > 0 && ~visited(v) % 如果u和v有连边且v未被访问过
alt = dist(u) + graph(u, v); % 计算起点经过u到v的距离
if alt < dist(v) % 如果新距离比原距离更短
dist(v) = alt; % 更新v的最短距离
path(v) = u; % 更新v的前驱节点为u
end
end
end
if visited(endNode) % 如果终点已被访问过,则可以提前结束循环
break;
end
end
if isinf(dist(endNode)) % 如果终点不可达,则无法构造路径
path = [];
else % 构造起点到终点的最短路径
pathNodes = endNode;
while pathNodes(1) ~= startNode
pathNodes = [path(pathNodes(1)), pathNodes];
end
path = [startNode, pathNodes];
end
end
```
调用示例:
```matlab
graph = [0 5 2 0 0; 5 0 0 4 2; 2 0 0 1 0; 0 4 1 0 3; 0 2 0 3 0];
[startNode, endNode] = deal(1, 5);
[dist, path] = dijkstra(graph, startNode, endNode);
disp(dist);
disp(path);
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)