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