Найдите все кратчайшие пути в биообъекте диаграмм
[dist] =
allshortestpaths(BGObj)
[dist] =
allshortestpaths(BGObj, ...'Directed', DirectedValue,
...)
[dist] = allshortestpaths(BGObj,
...'Weights', WeightsValue, ...)
BGObj | Биообъект диаграмм, созданный biograph Конструктор Object. |
DirectedValue | Свойство, которое указывает, направлен ли график или неориентированный. Введите false для неориентированного графа. Это приводит к верхнему треугольнику проигнорированной разреженной матрицы. Значением по умолчанию является true. |
WeightsValue | Вектор-столбец, который задает пользовательские веса для ребер в N на n матрице смежности, извлеченной из биообъекта диаграмм, BGObj. Это должно иметь одну запись для каждого ненулевого значения (ребро) в матрице. Порядок пользовательских весов в векторе должен совпадать с порядком ненулевых значений в матрице, когда это пересечено по столбцам. Это свойство позволяет вам использовать веса с нулевым знаком. По умолчанию, allshortestpaths получает информацию веса от ненулевых записей в матрице. |
Совет
Дополнительные сведения о функциях теории графов см. в Функциях Теории графов.
[ находит кратчайшие пути между каждой парой узлов в графике представленными N на n матрицей смежности извлеченный из биообъекта диаграмм, dist] =
allshortestpaths(BGObj)BGObj, использование алгоритма Джонсона. Ненулевые записи в матрице представляют веса ребер.
Выведите dist N на n матрица где dists, t S предназначаться для узла T. Элементами в диагонали этой матрицы всегда является 0, указание на исходный узел и целевой узел является тем же самым. 0 не в диагонали указывает, что расстоянием между исходным узлом и целевым узлом является 0. Inf указывает, что нет никакого пути между исходным узлом и целевым узлом.
Алгоритм Джонсона имеет временную сложность O(N*log(N)+N*E), где N и E количество узлов и ребер соответственно.
[...] = allshortestpaths ( вызовы BGObjPropertyName ', 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