主要内容

shortestpathtree

从节点到最短路径树

折叠所有页面

语法

TR = shortestpathtree (G, s)
TR = shortestpathtree (G s t)
TR=最短路径树(＿＿＿，名称，值）
(TR, D) = shortestpathtree (＿＿＿）
(TR, D, E) = shortestpathtree (＿＿＿）

描述

例子

TR= shortestpathtree (G，年代）返回一个有向图，TR，它包含从源节点开始的最短路径树年代到图中所有其他节点。如果图表是加权的(也就是说，G.边缘包含一个变量重量)，然后使用这些权重作为图中沿边的距离。否则，所有的边距离都取为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 4 6 6 7 8 7 5]；t=[2 3 4 5 6 1 8 1 3 2 8]；G=有向图（s，t）
G =具有属性的有向图:Edges: [13x1 table] Nodes: [8x0 table]

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

TR=最短路径树（G，1）；p=绘图（G）；高亮显示（p，TR，“EdgeColor”，“r”）

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

由于没有从节点1到节点7的路径，节点7将与树断开连接。

打开生活的脚本

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

创建并绘制图表。

S = [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 6 8 9 6 8 6 6 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）

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

找出从图中每个节点到节点10的最短路径。绘制结果树。

TR = shortestpathtree (G,“所有”,10); 绘图（TR）

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

打开生活的脚本

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

创建并绘制图表。

G=有向图（bucky）；绘图（G）

图中包含一个轴对象。axis对象包含一个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×52 . 5 .根据上下文选择正确答案
path_length = D (2)
路径长度=4

输入参数

全部折叠

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

例子:G=图（1,2）

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

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

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

  • 当与一起使用时t,年代和t输入必须满足:

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

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

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

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

标量

例子:1

向量

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

特征向量

例子:“一个”

字符向量的单元格数组

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

字符串标量

例子:“A”

字符串数组

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

年代必须不指定节点名“所有”，因为此节点名称与选项名称冲突。使用findnode而不是传递节点索引。

例子:最短路径树（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 '})

名称-值参数

指定可选的逗号分隔的对名称,值论据。的名字参数名和价值为对应值。的名字必须出现在引号内。可以以任意顺序指定多个名称和值对参数名称1，值1，…，名称，值．

例子:[TR，D]=最短路径树（G，s，t，'Method'，'unweighted'，'OutputForm'，'vector'）

输出格式，指定为逗号分隔对，由“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)是节点成功的节点IDk在路上k来t．按照惯例,TR (t) = 0．

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

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

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

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

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

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

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

  • “积极”用于所有图具有边权重且要求权重为非负的输入。此选项也用于有向图具有非负权边的输入。

  • “混合”用于有向图边权值为负值的输入。图不可能有负环。
“减重”

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

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

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

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

改进带加权边的有向无环图性能的算法。

使用isdag确认一个有向图是否是无圈图。

请注意

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

例子:最短路径（G，s，t，'Method'，'acyclic'）

输出参数

全部折叠

最短路径树，返回为有向图对象、单元格数组或向量，具体取决于“OutputForm”．使用突出函数可视化图上的最短路径树，或使用情节(TR)将最短路径树形象化。

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

源节点和目标节点之间的距离，以矢量形式返回。的值Inf表示两个节点之间没有路径。

的值，以逻辑向量、单元格数组或向量的形式返回树中或路径上的边“OutputForm”：

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

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

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

提示

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

    • 一个消极的循环是从节点返回自身的路径，路径上的边权重之和为负。如果负循环位于两个节点之间的路径上，则节点之间不存在最短路径，因为通过遍历负循环总是可以找到较短的路径。

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

另请参阅

||||

介绍了R2015b

MATLAB的文档

万博1manbetx

用MATLAB引入深度学习

用MATLAB引入深度学习

下载电子书