本页翻译不是最新的。点击此处可查看最新英文版本。

distances

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

全页折叠

语法

d = distances(G)
d = distances(G,s)
d = distances(G,s,t)
d = distances(___,'Method',algorithm)

说明

d = distances(G) 返回矩阵 d，其中 d(i,j) 是节点 i 和节点 j 之间的最短路径的长度。如果图进行了加权（即 G.Edges 包含变量 Weight），则这些权重用作沿图中各边的距离。否则，所有边距离都视为 1。

示例

d = distances(G,s) 将源节点限制为由 s 定义的节点，这样 d(i,j) 就是从节点 s(i) 到节点 j 的距离。

示例

d = distances(G,s,t) 还将目标节点限制为由 t 定义的节点，这样 d(i,j) 就是从节点 s(i) 到节点 t(j) 的距离。

示例

d = distances(___,'Method',algorithm) 可以使用上述语法中的任何输入参量指定在计算最短路径时使用的算法。例如，如果 G 是加权图，则 distances(G,'Method','unweighted') 将忽略 G 中的边权重，而将所有边权重视为 1。

示例

示例

全部折叠

打开实时脚本

创建并绘制一个图。

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

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

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

d = distances(G)
d = 10×10

     0     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     1     3     3     0     1     1     1     2     3
     3     2     4     4     1     0     2     2     3     4
     3     2     4     4     1     2     0     2     3     4
     3     2     4     4     1     2     2     0     1     2
     4     3     5     5     2     3     3     1     0     1
     5     4     6     6     3     4     4     2     1     0

d 是对称的，因为 G 为无向图。通常，d(i,j) 是节点 i 和节点 j 之间的最短路径长度，对于无向图，它等于 d(j,i)。

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

d(1,10)
ans = 
5
打开实时脚本

创建并绘制一个图。

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

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

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

d = distances(G,[1 2 3])
d = 3×7

     0     1     1     1     1     2     2
     1     0     1     2     2     1     2
     1     1     0     2     2     1     2

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

d(1,7)
ans = 
2
打开实时脚本

创建并绘制一个图。

s = [1 1 1 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 = graph(s,t);
plot(G)

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

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

sources = [5 7];
targets = [2 3];
d = distances(G,sources,targets)
d = 2×2

     3     1
     4     2

使用 d 求节点 7 和节点 3 之间的最短路径距离。在这种情况下，d(i,j) 是从节点 sources(i) 到节点 targets(j) 的距离。

d(2,2)
ans = 
2
打开实时脚本

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

s = [1 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 = digraph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight)

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

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

d = distances(G)
d = 8×8

     0    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   100    60    90     0   Inf
   Inf   100    20    20    10    10    50     0

由于 G 为有向图，d 是不对称的，且 d(i,j) 对应于节点 i 和 j 之间的距离。d 中的 Inf 值对应于不可达的节点。例如，由于节点 1 没有前趋节点，无法从图中的任何其他节点到达节点 1。因此，d 的第一列包含许多 Inf 值反映节点 1 不可达。

默认情况下，distances 使用边权重计算距离。指定 'Method' 为 'unweighted' 以忽略边权重并将所有边距离视为 1。

d1 = distances(G,'Method','unweighted')
d1 = 8×8

     0     1     1     1     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     4     0   Inf
   Inf     2     2     2     1     1     1     0

输入参数

全部折叠

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

示例: G = graph(1,2)

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

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

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

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

标量

示例：1

向量

示例：[1 2 3]

节点名称

字符向量

示例：'A'

字符向量元胞数组

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

字符串标量

示例："A"

字符串数组

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

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

示例: distances(G,[1 2])

示例: distances(G,'all',[1 3 5])

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

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

示例: distances(G,[1 2])

示例: distances(G,'all',[1 3 5])

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

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

'auto' 选项会自动选择算法：

  • 'unweighted' 用于没有边权重的 graph 和 digraph 输入。

  • 'positive' 用于具有边权重的所有 graph 输入，并要求权重为非负数。此选项还用于具有非负边权重的 digraph 输入。

  • 'mixed' 用于其边权重包含某些负值的 digraph 输入。图不能包含负循环。

'unweighted'

广度优先计算，将所有边权重都视为 1。

'positive'

迪杰斯特拉算法，要求所有边权重均为非负数。

'mixed'（仅适用于 digraph）

适用于有向图的 Bellman-Ford 算法，要求图没有负循环。

尽管对于相同的问题，'mixed' 的速度慢于 'positive'，但 'mixed' 更为通用，因为它允许某些边权重为负数。

注意

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

示例: distances(G,s,t,'Method','unweighted')

输出参量

全部折叠

节点对组之间的最短路径距离，以矩阵形式返回。d 的大小是：源节点数×目标节点数。值 Inf 表示路径不存在。

提示

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

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

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

扩展功能

全部展开

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

版本历史记录

在 R2015b 中推出

另请参阅

| | | |