Найдите все кратчайшие пути в биообъекте диаграмм
[
dist
] =
allshortestpaths(BGObj
)
[dist
] =
allshortestpaths(BGObj
, ...'Directed', DirectedValue
,
...)
[dist
] = allshortestpaths(BGObj
,
...'Weights', WeightsValue
, ...)
BGObj | Объект Biograph, созданный biograph Конструктор Object. |
DirectedValue | Свойство, которое указывает, направлен ли график или неориентированный. Введите false для неориентированного графа. Это приводит к верхнему треугольнику проигнорированной разреженной матрицы. Значением по умолчанию является true . |
WeightsValue | Вектор-столбец, который задает пользовательские веса для ребер в N на n матрице смежности, извлеченной из биообъекта диаграмм, BGObj . Это должно иметь одну запись для каждого ненулевого значения (ребро) в матрице. Порядок пользовательских весов в векторе должен совпадать с порядком ненулевых значений в матрице, когда это пересечено по столбцам. Это свойство позволяет вам использовать веса с нулевым знаком. По умолчанию, allshortestpaths получает информацию веса от ненулевых записей в матрице. |
Совет
Дополнительные сведения о функциях теории графов см. в Функциях Теории графов.
[
находит кратчайшие пути между каждой парой узлов в графике представленными N на n матрицей смежности извлеченный из биообъекта диаграмм, dist
] =
allshortestpaths(BGObj
)BGObj
, использование алгоритма Джонсона. Ненулевые записи в матрице представляют веса ребер.
Выведите dist
N на n матрица где
расстояние кратчайшего пути от исходного узла dist
s, t S
предназначаться для узла T
. Элементами в диагонали этой матрицы всегда является 0
, указание на исходный узел и целевой узел является тем же самым. 0
не в диагонали указывает, что расстоянием между исходным узлом и целевым узлом является 0
. Inf
указывает, что нет никакого пути между исходным узлом и целевым узлом.
Алгоритм Джонсона имеет временную сложность O(N*log(N)+N*E)
, где N
и E
количество узлов и ребер соответственно.
[...] = allshortestpaths (
вызовы BGObj
PropertyName
', PropertyValue
, ...)allshortestpaths
с дополнительными свойствами, которые используют имя свойства / пары значения свойства. Можно задать одно или несколько свойств в любом порядке. Каждый PropertyName
должен быть заключен в одинарные кавычки и нечувствительный к регистру. Это имя свойства / пары значения свойства следующие:
[
указывает, направлен ли график или неориентированный. Установите dist
] =
allshortestpaths(BGObj
, ...'Directed', DirectedValue
,
...)DirectedValue
к false
для неориентированного графа. Это приводит к верхнему треугольнику проигнорированной разреженной матрицы. Значением по умолчанию является true
.
[
позволяет вам задать пользовательские веса для ребер. dist
] = allshortestpaths(BGObj
,
...'Weights', WeightsValue
, ...)WeightsValue
вектор-столбец, имеющий одну запись для каждого ненулевого значения (ребро) в N на n матрице смежности, извлеченной из биообъекта диаграмм, BGObj
. Порядок пользовательских весов в векторе должен совпадать с порядком ненулевых значений в N на n матрице смежности, когда это пересечено по столбцам. Это свойство позволяет вам использовать веса с нулевым знаком. По умолчанию, allshortestpaths
получает информацию веса от ненулевых записей в N на n матрице смежности.
[1] Джонсон, D.B. (1977). Эффективные алгоритмы для кратчайших путей в разреженных сетях. Журнал ACM 24 (1), 1-13.
[2] Siek, J.G., Ли, L-Q и Lumsdaine, A. (2002). Руководство пользователя библиотеки графика повышения и справочник, (верхний Сэддл-Ривер, образование НДЖ:ПИРСОНА).
biograph
| conncomp
| graphallshortestpaths
| isdag
| isomorphism
| isspantree
| maxflow
| minspantree
| shortestpath
| topoorder
| traverse