最短路径问题的MATLAB例题和答案全解

以下是一个简单的 MATLAB 最短路径问题的例题和答案全解。

问题描述：

给定一个图，其中已知各个节点之间的距离，求从节点 1 到节点 5 的最短路径。

图示：

2 3
/ \ / \
1 4 6
\ / \ /
5 7

解答：

首先定义邻接矩阵，表示各个节点之间的距离：

distance = [
0 2 inf inf inf inf inf;
2 0 3 inf inf inf inf;
inf 3 0 inf 6 inf inf;
inf inf inf 0 4 3 inf;
inf inf 6 4 0 inf 5;
inf inf inf 3 inf 0 5;
inf inf inf inf 5 5 0
];

其中，0 表示节点到自身的距离为 0，inf 表示节点之间没有连接或不可达。

使用 Dijkstra 算法求解：

1. 初始化源节点和节点集：
- 将源节点的距离设置为 0；
- 将剩余节点的距离设置为 inf；
- 将所有节点加入未访问集合。

nodes = [1 2 3 4 5 6 7]; %所有节点
start = 1; %源节点
L = inf(1,7); %距离
L(start) = 0; %源节点距离为 0

2. 进行循环，直到所有节点都被访问：
- 从未访问集合中找到距离源节点最近的节点；
- 更新其相邻节点的距离。

while ~isempty(nodes) %未访问节点不为空
[~,i] = min(L(nodes)); %距离最小的节点
node = nodes(i); %当前节点
nodes(i) = []; %将节点从未访问节点中删除
for j = find(distance(node,:)<inf) %相邻节点
L(j) = min(L(j),L(node)+distance(node,j)); %更新距离
end
end

3. 输出从源节点到目标节点的最短路径：

goal = 5; %目标节点
path = goal; %建立路径数组
while path(1) ~= start %路径搜索
for j = find(distance(path(1),:)<inf) %相邻节点
if L(j) == L(path(1))-distance(path(1),j) %路径上的距离
path = [j path]; %添加节点到路径
break
end
end
end

disp(['从节点 ',num2str(start),' 到节点 ',num2str(goal),' 的最短路径为：',num2str(path)]);
disp(['距离为 ',num2str(L(goal))]);

输出结果：

从节点 1 到节点 5 的最短路径为：1 2 3 4 5
距离为 9

因此，从节点 1 到节点 5 的最短路径为 1-2-3-4-5，距离为 9。