distances
所有节点对组的最短路径距离
说明
示例
所有节点对组的最短路径距离
创建并绘制一个图。
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)
计算图中所有节点对组之间的最短路径距离。由于图边没有权重,所有边距离都视为 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)
求从节点 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)
求从节点 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)
求图节点的所有对组之间的最短路径距离。
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
输入参数
s
— 源节点
'all'
(默认) | 节点索引 | 节点名称
源节点,指定为一个或多个节点索引或节点名称,或指定为 'all'
以选择所有源节点。
下表显示通过数值节点索引或节点名称引用一个或多个节点的不同方法。
形式 | 单一节点 | 多个节点 |
---|---|---|
节点索引 | 标量 示例: | 向量 示例: |
节点名称 | 字符向量 示例: | 字符向量元胞数组 示例: |
字符串标量 示例: | 字符串数组 示例: |
s
和 t
不得指定名为 'all'
或 'Method'
的节点,因为这些节点名称与选项名称冲突。对于这些情况,请改用 findnode
传入节点索引。
示例: distances(G,[1 2])
示例: distances(G,'all',[1 3 5])
t
— 目标节点
'all'
(默认) | 节点索引 | 节点名称
目标节点,指定为一个或多个节点索引或节点名称,或指定为 'all'
以选择所有目标节点。
s
和 t
不得指定名为 'all'
或 'Method'
的节点,因为这些节点名称与选项名称冲突。对于这些情况,请改用 findnode
传入节点索引。
示例: distances(G,[1 2])
示例: distances(G,'all',[1 3 5])
algorithm
— 最短路径算法
'auto'
(默认) | 'unweighted'
| 'positive'
| 'mixed'
最短路径算法,指定为下表中的选项之一。
选项 | 描述 |
---|---|
'auto' (默认值) |
|
'unweighted' | 广度优先计算,将所有边权重都视为 |
'positive' | 迪杰斯特拉算法,要求所有边权重均为非负数。 |
'mixed' (仅适用于 digraph ) | 适用于有向图的 Bellman-Ford 算法,要求图没有负循环。 尽管对于相同的问题, |
注意
对于大多数图,'unweighted'
是速度最快的算法,然后是 'positive'
和 'mixed'
算法。
示例: distances(G,s,t,'Method','unweighted')
输出参量
d
— 节点对组之间的最短路径距离
矩阵
节点对组之间的最短路径距离,以矩阵形式返回。d
的大小是:源节点数×目标节点数。值 Inf
表示路径不存在。
提示
shortestpath
、shortestpathtree
和distances
函数不支持具有负边权重的无向图,或更通俗地说,不支持包含负循环的任何图,原因如下:负循环是从节点出发回到自身的路径,路径上的边权重之和为负值。如果两个节点之间的路径上具有负循环,则这两个节点之间不存在最短路径,因为始终可以通过遍历负循环找到更短路径。
无向图中的单个负边权重会创建一个负循环。
扩展功能
基于线程的环境
使用 MATLAB® backgroundPool
在后台运行代码或使用 Parallel Computing Toolbox™ ThreadPool
加快代码运行速度。
版本历史记录
在 R2015b 中推出
另请参阅
shortestpathtree
| shortestpath
| nearest
| graph
| digraph
MATLAB 命令
您点击的链接对应于以下 MATLAB 命令:
请在 MATLAB 命令行窗口中直接输入以执行命令。Web 浏览器不支持 MATLAB 命令。
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)