Найти все самые короткие пути в объекте-биографе
[dist] = allshortestpaths(BGObj)
[dist] = allshortestpaths(BGObj, ...'Directed', DirectedValue, ...)
[dist] = allshortestpaths(BGObj, ...'Weights', WeightsValue, ...)
BGObj | Объект-биограф, созданный biograph (конструктор объекта). |
DirectedValue | Свойство, указывающее, направлен или не направлен график. Войти false для неориентированного графа. Это приводит к игнорированию верхнего треугольника разреженной матрицы. По умолчанию: true. |
WeightsValue | Вектор столбца, задающий пользовательские веса для кромок в матрице смежности N-by-N, извлеченной из объекта-биографа. BGObj. Он должен иметь одну запись для каждого ненулевого значения (края) в матрице. Порядок пользовательских весов в векторе должен соответствовать порядку ненулевых значений в матрице, если она проходит по столбцам. Это свойство позволяет использовать веса с нулевым значением. По умолчанию allshortestpaths получает информацию о весе из ненулевых записей в матрице. |
Совет
Вводные сведения о функциях теории графов см. в разделе Функции теории графов.
[ находит кратчайшие пути между каждой парой узлов в графе, представленном матрицей близости N-на-N, извлеченной из объекта-биографа, dist] = allshortestpaths(BGObj)BGObj, используя алгоритм Джонсона. Ненулевые записи в матрице представляют веса краев.
Продукция dist - матрица N-на-N, где dist(S,T)S в целевой узел T. Элементы в диагонали этой матрицы всегда 0, указывая, что исходный узел и целевой узел одинаковы. A 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] Джонсон, Ди Би (1977). Эффективные алгоритмы для кратчайших путей в разреженных сетях. Журнал ACM 24 (1), 1-13.
[2] Сиек, Дж. Г., Ли, L-Q, и Люмсдейн, А. (2002). Руководство пользователя и справочное руководство библиотеки Boost Graph (Upper Saddle River, NJ: Pearson Education).
biograph | conncomp | graphallshortestpaths | isdag | isomorphism | isspantree | maxflow | minspantree | shortestpath | topoorder | traverse