Расстояния кратчайшего пути всех пар узла
d = distances(G)d, где d(i,j) длина кратчайшего пути между узлом i и узел j. Если график взвешивается (то есть, G.Edges содержит переменную Weight), затем те веса используются в качестве расстояний вдоль ребер в графике. В противном случае все расстояния ребра взяты, чтобы быть 1.
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
shortestpathshortestpathtree, и distances функции не поддерживают неориентированных графов с отрицательным весом ребра, или в более общем плане любой график, содержащий отрицательный цикл, по этим причинам:
Отрицательный цикл является путем, который ведет от узла назад к себе с суммой веса ребра на пути, являющемся отрицательным. Если отрицательный цикл находится на пути между двумя узлами, то никакой кратчайший путь не существует между узлами, поскольку более короткий путь может всегда находиться путем пересечения отрицательного цикла.
Один отрицательный вес ребра в неориентированном графе создает отрицательный цикл.
digraph | graph | nearest | shortestpath | shortestpathtree