Решите задачу кратчайшего пути в биообъекте диаграмм
[
dist
, path
, pred
] = shortestpath(BGObj
, S
)
[dist
, path
, pred
] = shortestpath(BGObj
, S
, T
)
[...] = shortestpath(..., 'Directed', DirectedValue
, ...)
[...] = shortestpath(..., 'Method', MethodValue
, ...)
[...] = shortestpath(..., 'Weights', WeightsValue
, ...)
BGObj | Биообъект диаграмм, созданный biograph Конструктор Object. |
S | Узел в графике, представленном N на n матрицей смежности, извлеченной из биообъекта диаграмм, BGObj . |
T | Узел в графике, представленном N на n матрицей смежности, извлеченной из биообъекта диаграмм, BGObj . |
DirectedValue | Свойство, которое указывает ли график, представленный N на n матрицей смежности, извлеченной из объекта биографика, BGObj , направлен или неориентированный. Введите false для неориентированного графа. Это приводит к верхнему треугольнику проигнорированной разреженной матрицы. Значением по умолчанию является true . |
MethodValue | Вектор символов или строка, которая задает алгоритм, раньше находили кратчайший путь. Выбор:
|
WeightsValue | Вектор-столбец, который задает пользовательские веса для ребер в N на n матрице смежности, извлеченной из биообъекта диаграмм, BGObj . Это должно иметь одну запись для каждого ненулевого значения (ребро) в N на n матрице смежности. Порядок пользовательских весов в векторе должен совпадать с порядком ненулевых значений в N на n матрице смежности, когда это пересечено по столбцам. Это свойство позволяет вам использовать веса с нулевым знаком. По умолчанию, shortestpaths получает информацию веса от ненулевых записей в N на n матрице смежности. |
Совет
Дополнительные сведения о функциях теории графов см. в Функциях Теории графов.
[
определяет кратчайшие пути одно источника из узла dist
, path
, pred
] = shortestpath(BGObj
, S
)S
ко всем другим узлам в графике, представленном N на n матрицей смежности, извлеченной из биообъекта диаграмм, BGObj
. Веса ребер являются всеми ненулевыми записями в N на n матрице смежности. dist
N
расстояния от источника до каждого узла (использующий Inf
s для недостижимых узлов и 0
для исходного узла). path
содержит пути к победе к каждому узлу. pred
содержит узлы-предшественников путей к победе.
[
определяет один одно источником целевой кратчайший путь из узла dist
, path
, pred
] = shortestpath(BGObj
, S
, T
)S
к узлу T
.
[...] = shortestpath (..., '
вызовы PropertyName
', PropertyValue
, ...)shortestpath
с дополнительными свойствами, которые используют имя свойства / пары значения свойства. Можно задать одно или несколько свойств в любом порядке. Каждый PropertyName
должен быть заключен в одинарные кавычки и нечувствительный к регистру. Это имя свойства / пары значения свойства следующие:
[...] = shortestpath(..., 'Directed',
указывает ли график, представленный N на n матрицей смежности, извлеченной из биообъекта диаграмм, DirectedValue
, ...)BGObj
, направлен или неориентированный. Установите DirectedValue
к false
для неориентированного графа. Это приводит к верхнему треугольнику проигнорированной разреженной матрицы. Значением по умолчанию является true
.
[...] = shortestpath(..., 'Method',
позволяет вам указать, что алгоритм раньше находил кратчайший путь. Выбор:MethodValue
, ...)
'Bellman-Ford'
— Принимает веса ребер, чтобы быть ненулевыми записями в N на n матрице смежности. Временной сложностью является O(N*E)
, где N
и E
количество узлов и ребер соответственно.
'BFS'
— Поиск в ширину. Принимает все веса, чтобы быть равными, и ненулевыми записями в N на n матрице смежности, чтобы представлять ребра. Временной сложностью является O(N+E)
, где N
и E
количество узлов и ребер соответственно.
'Acyclic'
— Принимает график, представленный N на n матрицей смежности, извлеченной из биообъекта диаграмм, BGObj
, чтобы быть направленным графом без петель и это взвешивает ребер, ненулевые записи в N на n матрице смежности. Временной сложностью является O(N+E)
, где N
и E
количество узлов и ребер соответственно.
'Dijkstra'
— Алгоритм по умолчанию. Принимает веса ребер, чтобы быть положительными значениями в N на n матрице смежности. Временной сложностью является O(log(N)*E)
, где N
и E
количество узлов и ребер соответственно.
[...] = shortestpath(..., 'Weights',
позволяет вам задать пользовательские веса для ребер. WeightsValue
, ...)WeightsValue
вектор-столбец, имеющий одну запись для каждого ненулевого значения (ребро) в N на n матрице смежности, извлеченной из биообъекта диаграмм, BGObj
. Порядок пользовательских весов в векторе должен совпадать с порядком ненулевых значений в N на n матрице смежности, когда это пересечено по столбцам. Это свойство позволяет вам использовать веса с нулевым знаком. По умолчанию, shortestpath
получает информацию веса от ненулевых записей в N на n матрице смежности.
[1] Дейкстра, E.W. (1959). Примечание по двум проблемам в связи с графиками. Numerische Mathematik 1, 269–271.
[2] Белман, Р. (1958). На проблеме маршрутизации. Ежеквартально прикладной математики 16 (1), 87–90.
[3] Siek, J.G., Ли, L-Q и Lumsdaine, A. (2002). Руководство пользователя библиотеки графика повышения и справочник, (верхний Сэддл-Ривер, образование НДЖ:ПИРСОНА).
allshortestpaths
| biograph
| conncomp
| graphshortestpath
| isdag
| isomorphism
| isspantree
| maxflow
| minspantree
| topoorder
| traverse