迪杰斯特拉算法实现matlab
时间: 2024-01-15 15:19:23 浏览: 33
迪杰斯特拉算法是一种用于求解最短路径的算法,可以在图中找到一个节点到其他所有节点的最短路径。下面是一个用MATLAB实现迪杰斯特拉算法的示例:
```matlab
function [dist, path] = dijkstra(graph, start)
n = size(graph, 1);
dist = inf(1, n);
dist(start) = 0;
visited = false(1, n);
path = cell(1, n);
for i = 1:n
u = findMinDist(dist, visited);
visited(u) = true;
for v = 1:n
if ~visited(v) && graph(u, v) > 0 && dist(u) + graph(u, v) < dist(v)
dist(v) = dist(u) + graph(u, v);
path{v} = [path{u}, v];
end
end
end
end
function u = findMinDist(dist, visited)
minDist = inf;
u = -1;
for i = 1:length(dist)
if ~visited(i) && dist(i) < minDist
minDist = dist(i);
u = i;
end
end
end
```
这个示例中,`graph`是一个邻接矩阵,表示图的连接关系,`start`是起始节点的索引。函数返回两个结果:`dist`是起始节点到每个节点的最短距离,`path`是起始节点到每个节点的最短路径。