shortestpath

两个单一节点之间的最短路径

语法

P = shortestpath(G,s,t)

P = shortestpath(G,s,t,'Method',algorithm)

[P,d] = shortestpath(___)

[P,d,edgepath] = shortestpath(___)

说明

P = shortestpath(G,s,t) 计算从源节点 s 处开始到目标节点 t 处结束的最短路径。如果图进行了加权（即 G.Edges 包含变量 Weight），则这些权重用作沿图中各边的距离。否则，所有边距离都视为 1。

P = shortestpath(G,s,t,'Method',algorithm) 可选择性地指定在计算最短路径时使用的算法。例如，如果 G 是加权图，则 shortestpath(G,s,t,'Method','unweighted') 将忽略 G 中的边权重，而将所有边权重视为 1。

[P,d] = shortestpath(___) 支持上述语法中的任何输入参量，且可返回最短路径的长度 d。

[P,d,edgepath] = shortestpath(___) 还返回从 s 到 t 的最短路径上所有边的边索引 edgepath。

示例

指定节点之间的最短路径

创建并绘制一个有向图。

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 = shortestpath(G,7,8)

P = 1×5

     7     1     3     5     8

加权图中的最短路径

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

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 = 1×5

     3     9     5     7     8

d = 4

由于图中心的边具有较大权重，节点 3 和 8 之间的最短路径围绕边权重最小的图边界。此路径的总长度为 4。

忽略边权重的最短路径

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

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 = 1×5

     6     3     1     4     8

d = 14

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

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

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

path2 = 1×3

     6     9     8

d = 2

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

多重图中的最短路径

绘制多重图中两个节点之间的最短路径，并突出显示经过的特定边。

创建一个具有五个节点的加权多重图。有几对节点之间的边数超过一条。绘制图作为参考。

G = graph([1 1 1 1 1 2 2 3 3 3 4 4],[2 2 2 2 2 3 4 4 5 5 5 2],[2 4 6 8 10 5 3 1 5 6 8 9]);
p = plot(G,'EdgeLabel',G.Edges.Weight);

找出节点 1 和节点 5 之间的最短路径。由于有几个节点对之间的边数超过一条，因此为 shortestpath 指定三个输出，以返回最短路径所经过的特定边。

[P,d,edgepath] = shortestpath(G,1,5)

P = 1×5

     1     2     4     3     5

d = 11

edgepath = 1×4

     1     7     9    10

结果表明最短路径的总长度为 11，并沿 G.Edges(edgepath,:) 指定的边前进。

G.Edges(edgepath,:)

ans=4×2 table
    EndNodes    Weight
    ________    ______

     1    2       2   
     2    4       3   
     3    4       1   
     3    5       5   

通过使用 highlight 函数和 'Edges' 名称-值对组指定经过的各条边的索引来突出显示这条边路径。

highlight(p,'Edges',edgepath)

根据节点坐标寻找最短路径

使用节点之间的距离作为边权重来寻找图中节点之间的最短路径。

创建一个包含 10 个节点的图。

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

为图节点创建 x 和 y 坐标。然后通过指定 'XData' 和 'YData' 名称-值对组，使用节点坐标绘制图。

x = [1 2 3 2 2.5 4 3 5 3 5];
y = [1 3 4 -1 2 3.5 1 3 0 1.5];
plot(G,'XData',x,'YData',y)

通过计算图节点之间的欧几里德距离，为图添加边权重。根据节点坐标 $\left({\mathit{x}}_{\mathit{i}},{\mathit{y}}_{\mathit{i}}\right)$ 计算距离，如下所示：

$$\mathit{d}=\sqrt{{\left|\Delta \mathit{x}\right|}^2+{\left|\Delta \mathit{y}\right|}^2}=\sqrt{{\left|{\mathit{x}}_{\mathit{s}}-{\mathit{x}}_{\mathit{t}}\right|}^2+{\left|{\mathit{y}}_{\mathit{s}}-{\mathit{y}}_{\mathit{t}}\right|}^2}.$$

要计算 $\Delta \mathit{x}$ 和 $\Delta \mathit{y}$，首先使用 findedges 获得说明图中每条边的源节点和目标节点的向量 sn 和 tn。然后使用 sn 和 tn 对 x 和 y 坐标向量进行索引，并计算 $\Delta \mathit{x}={\mathit{x}}_{\mathit{s}}-{\mathit{x}}_{\mathit{t}}$ 和 $\Delta \mathit{y}={\mathit{y}}_{\mathit{s}}-{\mathit{y}}_{\mathit{t}}$。hypot 函数计算平方和的平方根，因此指定 $\Delta \mathit{x}$ 和 $\Delta \mathit{y}$ 作为输入参量来计算每条边的长度。

[sn,tn] = findedge(G);
dx = x(sn) - x(tn);
dy = y(sn) - y(tn);
D = hypot(dx,dy);

将距离作为边权重添加到图中，并用带标签的边来重新绘制图。

G.Edges.Weight = D';
p = plot(G,'XData',x,'YData',y,'EdgeLabel',G.Edges.Weight);

计算节点 1 和节点 10 之间的最短路径，并指定两个输出来同时返回路径长度。对于加权图，shortestpath 自动使用考虑边权重的 'positive' 方法。

[path,len] = shortestpath(G,1,10)

path = 1×4

     1     4     9    10

len = 6.1503

使用 highlight 函数显示图中的路径。

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

输入参数

G — 输入图

graph 对象 | digraph 对象

输入图，指定为 graph 或 digraph 对象。可使用 graph 创建一个无向图，或使用 digraph 创建一个有向图。

示例: G = graph(1,2)

示例: G = digraph([1 2],[2 3])

s,t — 源节点 ID 和目标节点 ID（指定为单独的参量）

节点索引 | 节点名称

源节点 ID 和目标节点 ID，指定为节点索引或节点名称的单独参量。

值	示例
标量节点索引	1
字符向量节点名称	'A'
字符串标量节点名称	"A"

示例: shortestpath(G,2,5) 计算节点 2 和节点 5 之间的最短路径。

示例: shortestpath(G,'node1','node2') 计算命名节点 node1 和 node2 之间的最短路径。

algorithm — 最短路径算法

'auto' (默认) | 'unweighted' | 'positive' | 'mixed' | 'acyclic'

最短路径算法，指定为下表中的选项之一。

选项	描述
'auto'（默认值）	'auto' 选项会自动选择算法： 'unweighted' 用于没有边权重的 graph 和 digraph 输入。 'positive' 用于具有边权重的所有 graph 输入，并要求权重为非负数。此选项还用于具有非负边权重的 digraph 输入。 'mixed' 用于其边权重包含某些负值的 digraph 输入。图不能包含负循环。
'unweighted'	广度优先计算，将所有边权重都视为 1。
'positive'	迪杰斯特拉算法，要求所有边权重均为非负数。
'mixed'（仅适用于 digraph）	适用于有向图的 Bellman-Ford 算法，要求图没有负循环。 尽管对于相同的问题，'mixed' 的速度慢于 'positive'，但 'mixed' 更为通用，因为它允许某些边权重为负数。
'acyclic'（仅适用于 digraph）	算法旨在改进具有加权边的有向无环图 (DAG) 的性能。 使用 isdag 确认有向图是否无环。

注意

对于大多数图，'unweighted' 是速度最快的算法，然后是 'acyclic'、'positive' 和 'mixed'。

示例: shortestpath(G,s,t,'Method','acyclic')

输出参量

P — 节点之间的最短路径

节点索引 | 节点名称

节点之间的最短路径，以节点索引的向量或节点名称的数组形式返回。如果节点之间没有路径，则 P 为空，即 {}。

• 如果 s 和 t 包含数值节点索引，则 P 是节点索引的数值向量。

• 如果 s 和 t 包含节点名称，则 P 是包含节点名称的元胞数组或字符串数组。

如果 s 和 t 之间有多条最短路径，则 P 只包含其中一条路径。返回的路径可能根据 Method 指定的具体算法而有所不同。

d — 最短路径距离

标量

最短路径距离，以数值标量形式返回。d 是 P 中连续节点之间的边权重的总和。如果节点之间没有路径，则 d 是 Inf。

edgepath — 最短路径上的边

边索引向量

最短路径上的边，以边索引向量形式返回。对于多重图，此输出指示两个节点之间的哪条边位于该路径上。此输出与 highlight 的 'Edges' 名称-值对组兼容，例如：highlight(p,'Edges',edgepath)。

提示

• shortestpath、shortestpathtree 和 distances 函数不支持具有负边权重的无向图，或更通俗地说，不支持包含负循环的任何图，原因如下：

  • 负循环是从节点出发回到自身的路径，路径上的边权重之和为负值。如果两个节点之间的路径上具有负循环，则这两个节点之间不存在最短路径，因为始终可以通过遍历负循环找到更短路径。

  • 无向图中的单个负边权重会创建一个负循环。

扩展功能

C/C++ 代码生成

使用 MATLAB® Coder™ 生成 C 代码和 C++ 代码。

用法说明和限制：

• 名称-值参量必须为常量。

• 仅支持 'positive'、'unweighted' 和 'auto' 方法。

• 当指定节点之间没有路径时，输出 P 和 edgepath 的大小为 1×0，而不是 0×0。

基于线程的环境
使用 MATLAB® backgroundPool 在后台运行代码或使用 Parallel Computing Toolbox™ ThreadPool 加快代码运行速度。

版本历史记录

在 R2015b 中推出

另请参阅

shortestpathtree | distances | nearest | graph | digraph