主要内容

shortestpathtree

从节点出发的最短路径树

在页面中全部折叠

语法

TR = shortestpathtree (G, s)
TR = shortestpathtree (G s t)
TR = shortestpathtree (___、名称、值)
(TR, D) = shortestpathtree (___）
(TR, D, E) = shortestpathtree (___）

描述

例子

TR= shortestpathtree (G，年代）返回一个有向图，TR，其中包含从源节点开始的最短路径树年代到图中的所有其他节点。如果对图进行加权(即，G.Edges包含一个变量重量)，然后将这些权重用作图中沿边缘的距离。否则，所有的边缘距离被取为1．

例子

TR= shortestpathtree (G，年代，t）计算多个源节点或目标节点之间的最短路径树:

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

  • 年代可以指定多个源节点，并且t可以指定单个目标节点。

例子

TR= shortestpathtree (___，名称,值）使用由一个或多个名称-值对参数指定的附加选项，使用前面语法中的任何输入参数组合。例如,shortestpathtree (G s“OutputForm”,“矢量”)返回描述最短路径树的数字向量。

例子

［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 =有向图(s, t)
G =属性有向图:边:[13x1表]节点:[8x0表]

计算从节点1到图中其他可达节点的最短路径。然后，在图的顶部绘制结果树。

TR = shortestpathtree (G, 1);p =情节(G);突出(p, TR,“EdgeColor”，“r”）

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

由于节点1到节点7没有路径，因此节点7与树断开。

打开生活的脚本

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

创建并绘制一个图表。

S = [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 8 9 6 8 6 10 10 10 10 11 11 11 8 8];图G = (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];情节(G,“XData”, x,“YData”, y)

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

找出从图中每个节点到节点10的最短路径。画出生成的树。

TR = shortestpathtree (G,“所有”10);情节(TR)

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

打开生活的脚本

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

创建并绘制一个图表。

G =有向图(巴基);情节(G)

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

找出从节点23到其他几个节点的最短路径。指定OutputForm作为细胞返回单元格数组中的最短路径。指定两个输出也返回最短路径距离。

Target = [1 5 13 32 44];(TR, D) = shortestpathtree (G, 23岁的目标,“OutputForm”，“细胞”）
TR =5×1单元阵列{[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×55 4 7 5 5

树{j}从节点23到节点的最短路径是什么目标(j)长度为D (j)．

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

路径= TR {2}
路径=1×523 22 21 4 5
path_length = D (2)
path_length = 4

输入参数

全部折叠

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

例子:图G =(1、2)

例子:G =有向图([1 2]，[2 3])

源节点，指定为一个或多个节点索引或节点名称，或指定为图中的所有节点“所有”．

  • 当单独使用,年代必须指定单个源节点。

  • 当与t,年代而且t输入必须满足:

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

    • 年代可以指定多个源节点，并且t可以指定单个目标节点。

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

形式 单独的节点 多个节点
节点索引

标量

例子:1

向量

例子:(1 2 3)
节点名称

特征向量

例子:“一个”

字符向量的单元格数组

例子:{“A”“B”“C”}

字符串标量

例子:“一个”

字符串数组

例子:(“A”“B”“C”)

年代必须不指定节点名“所有”，因为此节点名称与选项名称冲突。使用findnode在这种情况下，要传入节点索引。

例子:shortestpathtree (G, a)

例子:shortestpathtree (G (1 2 3), 8)

目标节点，指定为一个或多个节点索引或节点名，或指定为图中的所有节点“所有”．

的年代而且t输入必须满足:

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

  • 年代可以指定多个源节点，并且t可以指定单个目标节点。

t必须不指定命名节点“所有”，“方法”,或“OutputForm”，因为这些节点名称与选项名称冲突。使用findnode为这些情况传入节点索引。

例子:shortestpathtree (G (1 2 3), 8)

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

名称-值参数

指定可选参数对为Name1 = Value1,…,以=家,在那里的名字参数名称和价值对应的值。名-值参数必须出现在其他参数之后，但对的顺序并不重要。

在R2021a之前，名称和值之间用逗号隔开，并括起来的名字在报价。

例子:(TR, D) = shortestpathtree (G s t,“方法”,“减重”、“OutputForm”,“矢量”)

输出的格式，指定为逗号分隔的对，由“OutputForm”表格中的一个选项。

选项 描述
“树”(默认)

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

TR是单元格数组，和TR {k}包含来自的路径年代来t (k)或从年代(k)来t．如果节点之间没有路径，那么TR {k}是空的。

如果年代而且t节点名是吗TR {k}是字符向量的单元格数组。否则,TR {k}是一个数字向量。

如果指定，则第三个输出E单元格数组是否指示每个对应路径上的边TR．
“向量”

TR是描述树的向量:

  • 如果年代那么，包含单个源节点TR (k)是node之前的节点IDk在从年代来k．按照惯例,TR (s) = 0．

  • 如果年代那么，包含多个源节点TR (k)是节点的ID，节点的成功k在从k来t．按照惯例,TR (t) = 0．

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

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

例子:shortestpathtree (G s“OutputForm”,“矢量”)

最短路径算法，指定为逗号分隔的对组成“方法”表格中的一个选项。

选项 描述
“汽车”(默认)

的“汽车”选项自动选择算法:

  • “减重”用于图而且有向图没有边权的输入。

  • “积极”用于所有图有边权值的输入，并且要求权值非负。此选项还用于有向图非负边权值的输入。

  • “混合”用于有向图边权值包含负值的输入。这个图不能有负循环。
“减重”

宽度优先计算，将所有边的权值视为1．
“积极”

要求所有边权为非负的Dijkstra算法。
“混合”(仅供有向图）

有向图的Bellman-Ford算法，它要求图没有负环。

而“混合”是低于“积极”对于同样的问题，“混合”更通用，因为它允许一些边的权值为负。
“单极”(仅供有向图）

为提高具有加权边的有向无环图(DAGs)性能而设计的算法。

使用isdag确定有向图是否无环。

请注意

对于大多数图形,“减重”是最快的算法，其次是“单极”，“积极”,“混合”．

例子:shortestpath (G s t,“方法”,“单极”)

输出参数

全部折叠

最短路径树，返回为有向图对象、单元格数组或向量的值“OutputForm”．使用突出函数将最短路径树可视化到图的某个图形的顶部，或使用情节(TR)将最短路径树形象化。

如果两个节点之间有多条最短路径，则TR只包含其中一个路径。返回的路径可以根据指定的算法而改变方法．的TR如果没有连接任何指定节点的路径，则输出为一个边为零的图。

源节点和目标节点之间的距离，作为向量返回。的值正表示两个节点之间没有路径。

的值，作为逻辑向量、单元格数组或向量返回“OutputForm”：

  • 如果你不指定“OutputForm”或指定的值“树”,然后E逻辑向量是否指示每条图边是否在有向图中TR．该输出与“边缘”名称-值对的突出,例如:突出(p,‘边缘’,E)．

  • 如果“OutputForm”是“细胞”,然后E单元格数组是否包含相应路径上的边TR．

  • 如果“OutputForm”是“向量”,然后E是一个向量，对于每个节点，它给出连接它到最短路径树中其父节点的边的索引。

提示

  • 的shortestpath，shortestpathtree,距离函数不支持具有负边权值的无向图，或者更普遍地说，不支持任何包含负循环的图，原因如下:

    • 一个消极的循环从节点返回自身的路径，该路径上的边权值之和为负。如果在两个节点之间的路径上有一个负循环，那么节点之间就不存在最短路径，因为通过遍历负循环总是可以找到更短的路径。

    • 无向图中的一个负边权值会产生一个负循环。

版本历史

介绍了R2015b

另请参阅

||||

Baidu
map