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