allshortestpaths (biograph)

Найдите все кратчайшие пути в биообъекте диаграмм

Синтаксис

[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 получает информацию веса от ненулевых записей в матрице.

Описание

Совет

Дополнительные сведения о функциях теории графов см. в Функциях Теории графов.

[dist] = allshortestpaths(BGObj) находит кратчайшие пути между каждой парой узлов в графике представленными N на n матрицей смежности извлеченный из биообъекта диаграмм, 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). Руководство пользователя библиотеки графика повышения и справочник, (верхний Сэддл-Ривер, образование НДЖ:ПИРСОНА).

Представленный в R2006b
Для просмотра документации необходимо авторизоваться на сайте