MATLAB 最短路

最短路

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

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

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

shortestpath 函数的语法如下：

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

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

例1

创建并绘制一个有向图。

1
2
3
4
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)

图1

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

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

结果：

1
2
3
4
5
P =
     7     1     3     5     8

d =
     4

例2

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

1
2
3
4
5
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)

图2

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

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

结果：

1
2
3
4
5
P =
     3     9     5     7     8

d =
     4

例3

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

1
2
3
4
5
6
7
8
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);

图3

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

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

结果：

1
2
3
4
5
path1 =
     6     3     1     4     8

d =
    14

以绿色加粗显示此路径。

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

图4

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

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

结果：

1
2
3
4
5
path2 =
     6     9     8

d =
     2

以红色加粗显示此路径。

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

图5