Самые короткие расстояния пути для всех пар узлов
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)
Вычислите самое короткое расстояние пути между всеми парами узлов в графике. Поскольку ребра графика не имеют весов, все расстояния ребра приняты равными 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. The Inf значения в d соответствуют узлам, которые недоступны. Для примера, поскольку узел 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
The shortestpath, shortestpathtree, и distances функции не поддерживают неориентированные графы с отрицательными весами ребер или вообще любой график, содержащий отрицательный цикл, по этим причинам:
Отрицательный цикл - это путь, который ведет от узла назад к себе, при этом сумма весов ребер на пути отрицательная. Если отрицательный цикл находится на пути между двумя узлами, то между узлами не существует кратчайшего пути, поскольку более короткий путь всегда можно найти, пройдя отрицательный цикл.
Один отрицательный вес ребра в неориентированном графе создает отрицательный цикл.
digraph | graph | nearest | shortestpath | shortestpathtree