shortestpath (biograph)

Решите задачу кратчайшего пути в биообъекте диаграмм

Синтаксис

[dist, path, pred] = shortestpath(BGObjS)
[dist, path, pred] = shortestpath(BGObjST)
[...] = 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Вектор символов или строка, которая задает алгоритм, раньше находили кратчайший путь. Выбор:
  • '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 количество узлов и ребер соответственно.

WeightsValueВектор-столбец, который задает пользовательские веса для ребер в N на n матрице смежности, извлеченной из биообъекта диаграмм, BGObj. Это должно иметь одну запись для каждого ненулевого значения (ребро) в N на n матрице смежности. Порядок пользовательских весов в векторе должен совпадать с порядком ненулевых значений в N на n матрице смежности, когда это пересечено по столбцам. Это свойство позволяет вам использовать веса с нулевым знаком. По умолчанию, shortestpaths получает информацию веса от ненулевых записей в N на n матрице смежности.

Описание

Совет

Дополнительные сведения о функциях теории графов см. в Функциях Теории графов.

[dist, path, pred] = shortestpath(BGObjS) определяет кратчайшие пути одно источника из узла S ко всем другим узлам в графике, представленном N на n матрицей смежности, извлеченной из биообъекта диаграмм, BGObj. Веса ребер являются всеми ненулевыми записями в N на n матрице смежности. dist N расстояния от источника до каждого узла (использующий Infs для недостижимых узлов и 0 для исходного узла). path содержит пути к победе к каждому узлу. pred содержит узлы-предшественников путей к победе.

[dist, path, pred] = shortestpath(BGObjST) определяет один одно источником целевой кратчайший путь из узла S к узлу T.

[...] = shortestpath (..., 'PropertyName', PropertyValue, ...) вызовы shortestpath с дополнительными свойствами, которые используют имя свойства / пары значения свойства. Можно задать одно или несколько свойств в любом порядке. Каждый PropertyName должен быть заключен в одинарные кавычки и нечувствительный к регистру. Это имя свойства / пары значения свойства следующие:

[...] = shortestpath(..., 'Directed', DirectedValue, ...) указывает ли график, представленный N на n матрицей смежности, извлеченной из биообъекта диаграмм, 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). Руководство пользователя библиотеки графика повышения и справочник, (верхний Сэддл-Ривер, образование НДЖ:ПИРСОНА).

Представленный в R2006b
Для просмотра документации необходимо авторизоваться на сайте