Кратчайший путь между двумя одним узлами
вычисляет кратчайший путь, запускающийся в исходном узле P
= shortestpath(G
,s,t
)s
и окончание в целевом узле t
. Если график взвешивается (то есть, G.Edges
содержит переменную Weight
), затем те веса используются в качестве расстояний вдоль ребер в графике. В противном случае все расстояния ребра взяты, чтобы быть 1
.
shortestpath
shortestpathtree
, и distances
функции не поддерживают неориентированных графов с отрицательным весом ребра, или в более общем плане любой график, содержащий отрицательный цикл, по этим причинам:
Отрицательный цикл является путем, который ведет от узла назад к себе с суммой веса ребра на пути, являющемся отрицательным. Если отрицательный цикл находится на пути между двумя узлами, то никакой кратчайший путь не существует между узлами, поскольку более короткий путь может всегда находиться путем пересечения отрицательного цикла.
Один отрицательный вес ребра в неориентированном графе создает отрицательный цикл.
digraph
| distances
| graph
| nearest
| shortestpathtree