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