Найдите все кратчайшие пути в биообъекте диаграмм
[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 матрицей, где 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