Дерево кратчайшего пути от узла
TR = shortestpathtree(G,s)TR, это содержит дерево кратчайших путей от исходного узла s ко всем другим узлам в графике. Если график взвешивается (то есть, G.Edges содержит переменную Weight), затем те веса используются в качестве расстояний вдоль ребер в графике. В противном случае все расстояния ребра взяты, чтобы быть 1.
TR = shortestpathtree(___,Name,Value)shortestpathtree(G,s,'OutputForm','vector') возвращает числовой вектор, который описывает дерево кратчайшего пути.
Найдите кратчайшие пути от исходного узла до каждого из других достижимых узлов в графике и постройте результаты.
Создайте ориентированного графа.
s = [1 1 2 3 3 4 4 6 6 7 8 7 5]; t = [2 3 4 4 5 5 6 1 8 1 3 2 8]; G = digraph(s,t)
G =
digraph with properties:
Edges: [13x1 table]
Nodes: [8x0 table]
Вычислите кратчайшие пути от узла 1 к каждому из других достижимых узлов в графике. Затем постройте получившееся дерево сверху графика.
TR = shortestpathtree(G,1); p = plot(G); highlight(p,TR,'EdgeColor','r')
С тех пор нет никакого пути от узла 1 к узлу 7, узел 7 отключается от дерева.
Найдите кратчайшие пути от каждого узла в графике к целевому узлу и постройте результаты.
Создайте и постройте график.
s = [1 1 1 1 1 1 1 2 2 7 7 7 7 9 9 3 3 1 6 4 8 10 6 8 4 5]; t = [2 3 4 5 6 8 7 6 7 5 6 8 9 6 8 6 10 10 10 10 10 11 11 11 8 8]; G = graph(s,t); x = [0 0.5 -0.5 -0.5 0.5 0 1.5 0 2 -1.5 -2]; y = [0 0.5 0.5 -0.5 -0.5 2 0 -2 0 0 0]; plot(G,'XData',x,'YData',y)
Найдите кратчайшие пути от каждого узла в графике к узлу 10. Постройте получившееся дерево.
TR = shortestpathtree(G,'all',10);
plot(TR)
Найдите кратчайшие пути и длины пути от одного исходного узла до нескольких целевых узлов.
Создайте и постройте график.
G = digraph(bucky); plot(G)
Найдите кратчайшие пути от узла 23 к нескольким другим узлам. Задайте OutputForm как cell возвратить кратчайшие пути в массиве ячеек. Задайте два выходных параметров, чтобы также возвратить расстояния кратчайшего пути.
target = [1 5 13 32 44]; [TR,D] = shortestpathtree(G,23,target,'OutputForm','cell')
TR=5×1 cell array
{[ 23 22 21 4 5 1]}
{[ 23 22 21 4 5]}
{[23 22 20 16 17 15 14 13]}
{[ 23 22 20 19 18 32]}
{[ 23 24 48 47 46 44]}
D = 1×5
5 4 7 5 5
tree{j} кратчайший путь от узла 23 к узлу target(j) с длиной D(j).
Найдите длину пути и длину пути от узла 21 к узлу 5.
path = TR{2}path = 1×5
23 22 21 4 5
path_length = D(2)
path_length = 4
shortestpathshortestpathtree, и distances функции не поддерживают неориентированных графов с отрицательным весом ребра, или в более общем плане любой график, содержащий отрицательный цикл, по этим причинам:
Отрицательный цикл является путем, который ведет от узла назад к себе с суммой веса ребра на пути, являющемся отрицательным. Если отрицательный цикл находится на пути между двумя узлами, то никакой кратчайший путь не существует между узлами, поскольку более короткий путь может всегда находиться путем пересечения отрицательного цикла.
Один отрицательный вес ребра в неориентированном графе создает отрицательный цикл.
shortestpath | distances | nearest | graph | digraph