Дерево кратчайшего пути от узла
возвращает ориентированного графа, 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