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