Дерево кратчайшего пути от узла
TR = shortestpathtree(G,s)
TR = shortestpathtree(G,s,t)
TR = shortestpathtree(___,Name,Value)
[TR,D] =
shortestpathtree(___)
[TR,D,E] =
shortestpathtree(___)
возвращает ориентированного графа, TR
= shortestpathtree(G
,s
)TR
, который содержит дерево кратчайших путей от исходного узла s
ко всем другим узлам в графике. Если график взвешивается (то есть, G.Edges
содержит переменную Weight
), то те веса используются в качестве расстояний вдоль ребер в графике. В противном случае все расстояния ребра взяты, чтобы быть 1
.
дополнительные опции использования заданы одним или несколькими Аргументами пары "имя-значение", с помощью любой из комбинаций входных аргументов в предыдущих синтаксисах. Например, TR
= shortestpathtree(___,Name,Value
)shortestpathtree(G,s,'OutputForm','vector')
возвращает числовой вектор, который описывает дерево кратчайшего пути.
shortestpath
, shortestpathtree
и функции distances
не поддерживают неориентированных графов с отрицательным весом ребра, или в более общем плане любой график, содержащий отрицательный цикл, по этим причинам:
Отрицательный цикл является путем, который ведет от узла назад к себе с суммой веса ребра на пути, являющемся отрицательным. Если отрицательный цикл находится на пути между двумя узлами, то никакой кратчайший путь не существует между узлами, поскольку более короткий путь может всегда находиться путем пересечения отрицательного цикла.
Один отрицательный вес ребра в неориентированном графе создает отрицательный цикл.
digraph
| distances
| graph
| nearest
| shortestpath