请编写一个初级的可在matlab2021运行的Dijkstra算法
时间: 2024-05-11 21:17:17 浏览: 76
以下是一个简单的Dijkstra算法的Matlab代码:
```matlab
function [D, P] = dijkstra(adj, start)
% 初始化
n = size(adj, 1);
D = Inf(1, n);
D(start) = 0;
P = zeros(1, n);
% 计算最短路径
for i = 1:n-1
[~, u] = min(D);
for v = 1:n
if adj(u, v) ~= 0 && D(u) + adj(u, v) < D(v)
D(v) = D(u) + adj(u, v);
P(v) = u;
end
end
D(u) = Inf;
end
end
```
其中,输入参数`adj`是一个邻接矩阵,表示图中各个节点之间的连通情况和边权重;`start`是起点的编号。函数返回值`D`是起点到各个节点的最短路径长度,`P`是最短路径上各个节点的前驱节点。
该算法的时间复杂度为$O(n^2)$,适用于小规模的图。若需要处理大规模的图,可以使用堆优化的Dijkstra算法,时间复杂度为$O(n\log n)$。
阅读全文