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