最短路径的Matlab代码
时间: 2023-12-24 11:47:29 浏览: 18
以下是一个使用Dijkstra算法求解最短路径的Matlab代码示例:
```matlab
function [dist, path] = dijkstra_shortest_path(adj_matrix, start_node, end_node)
% adj_matrix为邻接矩阵,start_node为起始节点,end_node为终止节点。
% dist返回起始节点到终止节点的最短距离,path返回最短路径上的节点序列。
num_nodes = size(adj_matrix, 1); %获取节点数量
dist = inf(1, num_nodes); %初始化距离数组
dist(start_node) = 0; %起始节点到自身的距离为0
visited = false(1, num_nodes); %初始化访问标记数组
path = zeros(1, num_nodes); %初始化路径数组
for i = 1:num_nodes
[~, cur_node] = min(dist + visited * inf); %选择最小距离的节点
visited(cur_node) = true; %将该节点标记为已访问
if isinf(dist(cur_node))
break; %如果没有连接到终止节点的路径,则跳出循环
end
neighbors = find(adj_matrix(cur_node, :)); %获取当前节点的所有邻居
for j = neighbors
alt = dist(cur_node) + adj_matrix(cur_node, j); %计算当前路径的总距离
if alt < dist(j) %如果当前路径更短,则更新距离数组和路径数组
dist(j) = alt;
path(j) = cur_node;
end
end
end
if isinf(dist(end_node))
path = []; %如果没有连接到终止节点的路径,则返回空路径
else
path(end) = end_node; %将终止节点添加到路径数组中
i = end_node;
while i ~= start_node %从终止节点向前遍历路径
i = path(i);
path = [i path];
end
end
end
```
使用方法:
1. 定义邻接矩阵`adj_matrix`,其中`adj_matrix(i,j)`表示节点i到节点j的距离(若两节点没有连接,则距离为无穷大)。
2. 调用函数`dijkstra_shortest_path(adj_matrix, start_node, end_node)`,其中`start_node`为起始节点的编号,`end_node`为终止节点的编号。
3. 函数返回最短路径的距离`dist`和节点序列`path`。如果不存在连接到终止节点的路径,则`path`为空。