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