主要内容

距离

所有节点对的最短路径距离

在页面中全部折叠

语法

d =距离(G)
d =距离(G, s)
d =距离(G s t)
d =距离(___“方法”,算法)

描述

例子

d=距离(G）返回一个矩阵,d,在那里d (i, j)节点之间最短路径的长度是多少我和节点j．如果对图进行加权(即，G.Edges包含一个变量重量)，然后将这些权重用作图中沿边缘的距离。否则，所有的边缘距离被取为1．

例子

d=距离(G，年代）的定义的节点限制源节点年代,这样d (i, j)是到节点的距离吗(我)到节点j．

例子

d=距离(G，年代，t）此外，将目标节点限制为定义的节点t,这样d (i, j)是到节点的距离吗(我)到节点t (j)．

例子

d=距离(___“方法”,算法）可选地指定在使用前面语法中的任何输入参数计算最短路径时使用的算法。例如,如果G那么是加权图吗距离(G,“方法”,“减重”)忽略边的权重G而是把所有边的权值都看成1．

例子

全部折叠

打开生活的脚本

创建并绘制一个图表。

S = [1 1 1 2 5 5 5 8 9];T = [2 3 4 5 6 7 8 9 10];图G = (s, t);情节(G)

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

计算图中所有节点对之间的最短路径距离。由于图的边没有权值，所以所有的边距离都取为1。

d =距离(G)
d =10×100 1 1 1 2 3 3 3 4 5 1 0 2 2 1 2 2 2 3 4 1 2 0 2 3 4 4 4 5 6 1 2 2 0 3 4 4 4 5 6 2 3 3 0 1 1 1 2 3 3 1 2 4 4 0 2 2 3 4 3 2 4 4 1 2 0 2 3 4 3 2 4 1 2 2 0 1 2 3 4 5 5 4 2 3 3 1 0 5 6 6 3 4 4 2 1 0

d是对称的,因为G是一个无向图。在一般情况下d (i, j)节点之间最短路径的长度是多少我和节点j，对于无向图，这等价于d (j,我)．

例如，求节点1到节点10之间最短路径的长度。

d (10)
ans = 5
打开生活的脚本

创建并绘制一个图表。

S = [1 1 1 2 2 3 4 4 5 6];T = [2 3 4 5 3 6 6 5 7 7];图G = (s, t);情节(G)

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

求节点1、节点2和节点3到图中所有其他节点的最短路径距离。

d =距离(G，[1 2 3])
d =3×70 1 1 1 1 2 2 1 0 1 2 2 1 2 1 1 1 2 2

使用d求节点1到节点7的最短路径距离。

d (7)
ans = 2
打开生活的脚本

创建并绘制一个图表。

S = [1 11 2 2 3 3 4 5 5 6 7 8 8 10 11];T = [2 3 10 4 12 5 4 6 6 7 9 8 9 11 11 12];图G = (s, t);情节(G)

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

求从节点5和7到节点2和3的最短路径距离。

来源= [5 7];Targets = [2 3];d =距离(G、来源、目标)
d =2×23 1 4 2

使用d求节点7到节点3之间的最短路径距离。在这种情况下,d (i, j)是到节点的距离吗来源(我)到节点目标(j)．

d (2, 2)
ans = 2
打开生活的脚本

创建并绘制带有加权边的有向图。

S = [1 1 2 5 3 6 4 7 8 8 8];T = [2 3 4 5 3 6 4 7 2 6 7 5];Weights = [100 10 10 10 10 20 10 30 50 10 70 10];G =有向图(s t重量);情节(G,“EdgeLabel”G.Edges.Weight)

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

求所有图节点对之间的最短路径距离。

d =距离(G)
d =8×80 90 10 10 100 30 40 Inf Inf 0 20 50 10 40 80 Inf Inf 110 0 30 120 20 60 Inf Inf 80 100 0 90 120 30 Inf Inf 120 10 40 0 30 70 Inf Inf 90 110 10 100 0 40 Inf Inf 50 70 10 10 50 0

自G是有向图，d是不对称的，和d (i, j)对应于节点之间的距离我而且j．的正值d与不可达节点对应。例如，由于节点1没有前一个节点，所以不可能从图中的任何其他节点到达节点1。第一列d包含了许多正值，以反映节点1不可达。

默认情况下,距离使用边权值来计算距离。指定“方法”作为“减重”忽略边的权值并将所有边的距离都视为1。

d1 =距离(G,“方法”，“减重”）
d1 =8×80 1 1 1 2 2 2 2 2 Inf Inf 0 2 4 1 3 5 Inf Inf 4 0 2 5 1 3 Inf Inf 2 4 0 3 5 1 Inf Inf 5 1 3 0 2 4 Inf Inf 3 5 1 4 0 2 Inf Inf 1 3 5 2 1 1 1 1 1

输入参数

全部折叠

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

例子:图G =(1、2)

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

源节点，指定为一个或多个节点索引或节点名称，或“所有”选择所有源节点。

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

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

标量

例子:1

向量

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

特征向量

例子:“一个”

字符向量的单元格数组

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

字符串标量

例子:“一个”

字符串数组

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

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

例子:距离(G, 1 [2])

例子:距离(G,“所有”,[1 3 5])

目标节点，指定为一个或多个节点索引或节点名称，或“所有”选择所有目标节点。

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

例子:距离(G, 1 [2])

例子:距离(G,“所有”,[1 3 5])

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

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

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

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

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

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

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

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

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

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

请注意

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

例子:距离(G s t,“方法”,“减重”)

输出参数

全部折叠

节点对之间的最短路径距离，作为矩阵返回。的大小dIs(#源节点)-by-(#目标节点)。的值正表示不存在的路径。

提示

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

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

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

版本历史

介绍了R2015b

另请参阅

||||

Baidu
map