Расстояния кратчайшего пути всех пар узла
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 9]; t = [2 3 4 5 6 7 8 9 10 11]; G = graph(s,t); plot(G)
Вычислите расстояние кратчайшего пути между всеми парами узла в графике. Поскольку края графика не имеют весов, все граничные расстояния взяты, чтобы быть 1.
d = distances(G)
d = 11×11
0 1 1 1 2 3 3 3 4 5 5
1 0 2 2 1 2 2 2 3 4 4
1 2 0 2 3 4 4 4 5 6 6
1 2 2 0 3 4 4 4 5 6 6
2 1 3 3 0 1 1 1 2 3 3
3 2 4 4 1 0 2 2 3 4 4
3 2 4 4 1 2 0 2 3 4 4
3 2 4 4 1 2 2 0 1 2 2
4 3 5 5 2 3 3 1 0 1 1
5 4 6 6 3 4 4 2 1 0 2
⋮
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 не поддерживают неориентированных графов с отрицательным весом ребра, или более широко любой график, содержащий отрицательный цикл, по этим причинам:
Отрицательный цикл является путем, который ведет от узла назад к себе с суммой веса ребра на пути, являющемся отрицательным. Если отрицательный цикл находится на пути между двумя узлами, то никакой кратчайший путь не существует между узлами, поскольку более короткий путь может всегда находиться путем пересечения отрицательного цикла.
Один отрицательный вес ребра в неориентированном графе создает отрицательный цикл.
диграф | график | самый близкий | кратчайший путь | shortestpathtree