Main Content

shortestpathtree

从节点的最短路径树

全页折叠

语法

TR = shortestpathtree(G,s)
TR = shortestpathtree(G,s,t)
TR = shortestpathtree(___,Name,Value)
[TR,D] = shortestpathtree(___)
[TR,D,E] = shortestpathtree(___)

说明

TR = shortestpathtree(G,s) 返回有向图 TR，其中包含从源节点 s 到图中所有其他节点的最短路径树。如果图进行了加权（即 G.Edges 包含变量 Weight），则这些权重用作沿图中各边的距离。否则，所有边距离都视为 1。

示例

TR = shortestpathtree(G,s,t) 计算多个源或目标节点之间的最短路径树：

  • s 可以是单个源节点，t 可以指定多个目标节点。

  • s 可以指定多个源节点，t 可以指定单个目标节点。

示例

TR = shortestpathtree(___,Name,Value) 使用由一个或多个名称-值对组参量指定的其他选项，这些选项使用上述语法中的任意输入参量组合。例如，shortestpathtree(G,s,'OutputForm','vector') 返回用于描述最短路径树的数值向量。

示例

[TR,D] = shortestpathtree(___) 还返回树中各节点之间的最短路径距离。

示例

[TR,D,E] = shortestpathtree(___) 还返回逻辑向量 E，指示图中的每条边是否在 TR 中。

示例

全部折叠

打开实时脚本

求从一个源节点到图中每个其他可达节点的最短路径，并绘制结果。

创建一个有向图。

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)
G = 
  digraph with properties:

    Edges: [13x1 table]
    Nodes: [8x0 table]

计算从节点 1 到图中每个其他可达节点的最短路径。然后，在图上绘制所得到的树。

TR = shortestpathtree(G,1);
p = plot(G);
highlight(p,TR,'EdgeColor','r')

Figure contains an axes object. The axes object contains an object of type graphplot.

由于不存在从节点 1 到节点 7 的路径，节点 7 从树中断开连接。

打开实时脚本

求从图中每个节点到一个目标节点的最短路径，并绘制结果。

创建并绘制一个图。

s = [1 1 1 1 1 1 1 2 2 7 7 7 7 9 9 3 3 1 6 4 8 10 6 8 4 5];
t = [2 3 4 5 6 8 7 6 7 5 6 8 9 6 8 6 10 10 10 10 10 11 11 11 8 8];
G = graph(s,t);
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];
plot(G,'XData',x,'YData',y)

Figure contains an axes object. The axes object contains an object of type graphplot.

查找从图中每个节点到节点 10 的最短路径。绘制所得到的树。

TR = shortestpathtree(G,'all',10);
plot(TR)

Figure contains an axes object. The axes object contains an object of type graphplot.

打开实时脚本

求从单一源节点到多个目标节点的最短路径和路径长度。

创建并绘制一个图。

G = digraph(bucky);
plot(G)

Figure contains an axes object. The axes object contains an object of type graphplot.

求从节点 23 到多个其他节点的最短路径。将 OutputForm 指定为 cell，以元胞数组形式返回最短路径。指定两个输出以同时返回最短路径距离。

target = [1 5 13 32 44];
[TR,D] = shortestpathtree(G,23,target,'OutputForm','cell')
TR=5×1 cell array
    {[         23 22 21 4 5 1]}
    {[           23 22 21 4 5]}
    {[23 22 20 16 17 15 14 13]}
    {[      23 22 20 19 18 32]}
    {[      23 24 48 47 46 44]}


D = 1×5

     5     4     7     5     5

tree{j} 是从节点 23 到节点 target(j) 的最短路径，长度为 D(j)。

求从节点 21 到节点 5 的路径和路径长度。

path = TR{2}
path = 1×5

    23    22    21     4     5


path_length = D(2)
path_length = 
4

输入参数

全部折叠

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

示例: G = graph(1,2)

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

源节点，指定为一个或多个节点索引或节点名称，或者指定为 'all' 表示图中的所有节点。

  • 在单独使用时，s 必须指定单一源节点。

  • 与 t 一起使用时，s 和 t 输入必须满足以下条件：

    • s 可以是单个源节点，t 可以指定多个目标节点。

    • s 可以指定多个源节点，t 可以指定单个目标节点。

下表显示通过数值节点索引或节点名称引用一个或多个节点的不同方法。

形式单一节点多个节点
节点索引

标量

示例：1

向量

示例：[1 2 3]

节点名称

字符向量

示例：'A'

字符向量元胞数组

示例：{'A' 'B' 'C'}

字符串标量

示例："A"

字符串数组

示例：["A" "B" "C"]

s 不得指定节点名称 'all'，因为此节点名称与选项名称冲突。对于这种情况，请改用 findnode 传入节点索引。

示例: shortestpathtree(G,'a')

示例: shortestpathtree(G,[1 2 3],8)

目标节点，指定为一个或多个节点索引或节点名称，或者指定为 'all' 表示图中的所有节点。

s 和 t 输入必须满足以下条件：

  • s 可以是单个源节点，t 可以指定多个目标节点。

  • s 可以指定多个源节点，t 可以指定单个目标节点。

t 不得指定名为 'all'、'Method' 或 'OutputForm' 的节点，因为这些节点名称与选项名称冲突。对于这些情况，请改用 findnode 传入节点索引。

示例: shortestpathtree(G,[1 2 3],8)

示例: shortestpathtree(G,{'a','b','c'},{'f'})

名称-值参数

将可选的参量对组指定为 Name1=Value1,...,NameN=ValueN，其中 Name 是参量名称，Value 是对应的值。名称-值参量必须出现在其他参量之后，但参量对组的顺序无关紧要。

在 R2021a 之前，使用逗号分隔每个名称和值，并用引号将 Name 引起来。

示例: [TR,D] = shortestpathtree(G,s,t,'Method','unweighted','OutputForm','vector')

输出的格式，指定为逗号分隔的对组，其中包含 'OutputForm' 和下表中的选项之一。

选项描述
'tree'（默认值）

TR 是表示最短路径树的有向图。如果指定，则第三个输出 E 是一个逻辑向量，指示每条边是否在 TR 中。

'cell'

TR 是一个元胞数组，TR{k} 包含从 s 到 t(k) 或从 s(k) 到 t 的路径。如果节点之间无路径，则 TR{k} 为空。

如果 s 和 t 为节点名称，则 TR{k} 是字符向量元胞数组。否则，TR{k} 是数值向量。

如果指定，则第三个输出 E 是一个元胞数组，指示 TR 中每条对应路径上的边。

'vector'

TR 是用于描述树的向量：

  • 如果 s 只包含一个源节点，则 TR(k) 是从 s 到 k 的路径上的节点 k 之前的节点的 ID。按照惯例，TR(s) = 0。

  • 如果 s 包含多个源节点，则 TR(k) 是从 k 到 k 的路径上的节点 t 之后的节点的 ID。按照惯例，TR(t) = 0。

在每种情况下，如果节点 k 不是树的一部分，则 TR(k) 是 NaN。

如果指定，则第三个输出 E 是一个向量，其中 E(k) 给出连接节点 k 和节点 TR(k) 的最短路径树的边索引。

示例: shortestpathtree(G,s,'OutputForm','vector')

最短路径算法，指定为逗号分隔的对组，其中包含 'Method' 和下表中的选项之一。

选项描述
'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')

输出参量

全部折叠

最短路径树，以 digraph 对象、元胞数组或向量形式返回，具体取决于 'OutputForm' 的值。使用 highlight 函数以可视化形式在绘制的图上呈现最短路径树，或使用 plot(TR) 以可视化形式单独呈现最短路径树。

如果两个节点之间有多条最短路径，则 TR 只包含其中一条路径。返回的路径可能根据 Method 指定的具体算法而有所不同。如果没有连接到任何指定节点的路径，则 TR 输出是具有零条边的图。

源和目标节点之间的距离，以向量形式返回。值 Inf 表示两个节点之间不存在路径。

树或路径上的边，以逻辑向量、元胞数组或向量形式返回，具体取决于 'OutputForm' 的值：

  • 如果不指定 'OutputForm' 或者指定了 'tree' 的值，则 E 是一个逻辑向量，指示图中的每条边是否在有向图 TR 中。此输出与 highlight 的 'Edges' 名称-值对组兼容，例如：highlight(p,'Edges',E)。

  • 如果 'OutputForm' 为 'cell'，则 E 是一个元胞数组，其中包含 TR 中对应路径上的边。

  • 如果 'OutputForm' 为 'vector'，则 E 是一个向量，给出最短路径树中将每个节点连接到父节点的边的索引。

提示

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

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

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

扩展功能

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

版本历史记录

在 R2015b 中推出

另请参阅

| | | |