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