MATLAB 最短路

时间:2023-02-08 13:50:57
MATLAB 最短路

✅作者简介:人工智能专业本科在读,喜欢计算机与编程,写博客记录自己的学习历程。
????个人主页:小嗷犬的个人主页
????个人网站:小嗷犬的技术小站
????个人信条:为天地立心,为生民立命,为往圣继绝学,为万世开太平。



最短路

最短路是指在一个有向图中,从一个顶点到另一个顶点的最短路径。在数学建模中,最短路问题可以用来表示物流运输问题,例如:从一个城市到另一个城市的最短路程,从一个城市到另一个城市的最短时间,从一个城市到另一个城市的最少运输成本等等。

如何使用 MATLAB 解决最短路问题

MATLAB 中的最短路问题可以使用 shortestpath 函数来解决。

shortestpath 函数的语法如下:

[P,d] = shortestpath(G,s,t)

其中,G 是一个图,s 是起点,t 是终点,P 是从起点到终点的最短路径,d 是从起点到终点的最短路径的长度。

例1

创建并绘制一个有向图。

s = [1 1 2 3 3 4 4 6 6 7 8 7 5];
t = [2 3 4 4 5 5 6 1 8 1 3 2 8];
G = digraph(s,t);
plot(G)

MATLAB 最短路

计算节点 7 和 8 之间的最短路径。

[P,d] = shortestpath(G,7,8)

结果:

P =
     7     1     3     5     8

d =
     4

例2

创建并绘制一个具有加权边的图。

s = [1 1 1 2 2 6 6 7 7 3 3 9 9 4 4 11 11 8];
t = [2 3 4 5 6 7 8 5 8 9 10 5 10 11 12 10 12 12];
weights = [10 10 10 10 10 1 1 1 1 1 1 1 1 1 1 1 1 1];
G = graph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight)

MATLAB 最短路

求节点 3 和 8 之间的最短路径,并指定两个输出以同时返回该路径的长度。

[P,d] = shortestpath(G,3,8)

结果:

P =
     3     9     5     7     8

d =
     4

例3

使用自定义节点坐标创建并绘制一个具有加权边的图。

s = [1 1 1 1 1 2 2 7 7 9 3 3 1 4 10 8 4 5 6 8];
t = [2 3 4 5 7 6 7 5 9 6 6 10 10 10 11 11 8 8 11 9];
weights = [1 1 1 1 3 3 2 4 1 6 2 8 8 9 3 2 10 12 15 16];
G = graph(s,t,weights);

x = [0 0.5 -0.5 -0.5 0.5 0 1.5 0 2 -1.5 -2];
y = [0 0.5 0.5 -0.5 -0.5 2 0 -2 0 0 0];
p = plot(G,'XData',x,'YData',y,'EdgeLabel',G.Edges.Weight);

MATLAB 最短路

根据图边权重,求节点 6 和 8 之间的最短路径。

[path1,d] = shortestpath(G,6,8)

结果:

path1 =
     6     3     1     4     8

d =
    14

以绿色加粗显示此路径。

highlight(p,path1,'EdgeColor','g','LineWidth',2)

MATLAB 最短路

将 Method 指定为 unweighted 以忽略边权重,转而将所有边的权重都视为 1。此方法会在节点之间生成一条不同路径,该路径以前因长度太大而不能成为最短路径。

[path2,d] = shortestpath(G,6,8,'Method','unweighted')

结果:

path2 =
     6     9     8

d =
     2

以红色加粗显示此路径。

highlight(p,path2,'EdgeColor','r','LineWidth',2)

MATLAB 最短路