✅作者简介：人工智能专业本科在读，喜欢计算机与编程，写博客记录自己的学习历程。
????个人主页：小嗷犬的个人主页
????个人网站：小嗷犬的技术小站
????个人信条：为天地立心，为生民立命，为往圣继绝学，为万世开太平。
本文目录
最短路
最短路是指在一个有向图中，从一个顶点到另一个顶点的最短路径。在数学建模中，最短路问题可以用来表示物流运输问题，例如：从一个城市到另一个城市的最短路程，从一个城市到另一个城市的最短时间，从一个城市到另一个城市的最少运输成本等等。
如何使用 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)
计算节点 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)
求节点 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);
根据图边权重，求节点 6 和 8 之间的最短路径。
[path1,d] = shortestpath(G,6,8)
结果：
path1 =
6 3 1 4 8
d =
14
以绿色加粗显示此路径。
highlight(p,path1,'EdgeColor','g','LineWidth',2)
将 Method 指定为 unweighted 以忽略边权重，转而将所有边的权重都视为 1。此方法会在节点之间生成一条不同路径，该路径以前因长度太大而不能成为最短路径。
[path2,d] = shortestpath(G,6,8,'Method','unweighted')
结果：
path2 =
6 9 8
d =
2
以红色加粗显示此路径。
highlight(p,path2,'EdgeColor','r','LineWidth',2)
