Решите проблему кратчайшего пути в биообъекте диаграмм
[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