最短路径问题的MATLAB带图片例题和答案全解
时间: 2023-05-24 08:04:13 浏览: 62
这里为您提供一个最短路径问题的 MATLAB 带图片例题和答案全解:
【例题】一张地图如图所示,从起点 A 到终点 B,求最短路线。
![map](https://img-blog.csdn.net/20180416171416324)
【解答】
1. 用矩阵表示地图:
```MATLAB
map = [0, 2, 0, 0, 0, 0, 0, 0, 0;
2, 0, 3, 0, 0, 0, 0, 0, 0;
0, 3, 0, 4, 4, 0, 0, 0, 0;
0, 0, 4, 0, 3, 0, 0, 0, 0;
0, 0, 4, 3, 0, 2, 0, 0, 0;
0, 0, 0, 0, 2, 0, 3, 3, 0;
0, 0, 0, 0, 0, 3, 0, 2, 0;
0, 0, 0, 0, 0, 3, 2, 0, 2;
0, 0, 0, 0, 0, 0, 0, 2, 0];
```
其中,0 表示两点不直接相连,其他数表示两点之间的距离。
2. 用 Dijkstra 算法求最短路线:
```MATLAB
start_point = 1; % 起点
end_point = 2; % 终点
distance = inf(1, 9); % 到各点的距离(初始值为无穷大)
distance(start_point) = 0; % 起点到起点的距离为 0
visited = zeros(1, 9); % 是否访问过(初始值为 0)
path = zeros(1, 9); % 路径(初始值为 0,表示无路径)
for i = 1:8
% 找到未访问过的距离最小的点
min_dist = inf; % 最小距离
u = -1; % 最小距离的点
for j = 1:9
if ~visited(j) && distance(j) < min_dist
min_dist = distance(j);
u = j;
end
end
if u == -1 % 未找到符合条件的点,跳出循环
break;
end
visited(u) = 1; % 标记为已访问
% 更新距离
for v = 1:9
if ~visited(v) && map(u, v) > 0 && distance(u) + map(u, v) < distance(v)
distance(v) = distance(u) + map(u, v);
path(v) = u;
end
end
end
% 输出最短路线
path_str = sprintf('%d', end_point);
current_p = end_point;
while path(current_p) ~= start_point
path_str = strcat(sprintf('%d', path(current_p)), '->', path_str);
current_p = path(current_p);
end
path_str = strcat(sprintf('%d', start_point), '->', path_str);
fprintf('最短路线:%s\n', path_str);
```
最短路线:1->2。
3. 画出最短路线:
```MATLAB
x = [200, 100, 0, 0, 100, 200, 300, 300, 200]; % 横坐标
y = [0, 100, 200, 300, 400, 400, 300, 200, 200]; % 纵坐标
h = figure(1); % 新建图形
set(h, 'position', [100, 100, 400, 500]); % 设置图形大小和位置
hold on; % 启动画图保持功能
axis equal; % 设置横纵坐标比例相同
plot(x, y, 'k-'); % 画出地图
% 画出起点和终点
plot(x(start_point), y(start_point), 'ro', 'MarkerSize', 8, 'LineWidth', 2);
plot(x(end_point), y(end_point), 'r*', 'MarkerSize', 8, 'LineWidth', 2);
% 画出最短路线
current_p = end_point;
while path(current_p) ~= start_point
plot([x(current_p), x(path(current_p))], [y(current_p), y(path(current_p))], 'r-', 'LineWidth', 2);
current_p = path(current_p);
end
plot([x(current_p), x(path(current_p))], [y(current_p), y(path(current_p))], 'r-', 'LineWidth', 2);
text(x(start_point), y(start_point)+10, 'A'); % 标注 A
text(x(end_point), y(end_point)-10, 'B'); % 标注 B
```
结果如图所示:
![map_answer](https://img-blog.csdn.net/20180416172304113)