одномоментная дорожка (биограф)

Решение проблемы кратчайшего пути в объекте-биографе

Синтаксис

[dist, path, pred] = shortestpath(BGObj, S) [dist, path, pred] = shortestpath(BGObj, S, T) [...] = shortestpath(..., 'Directed', DirectedValue, ...) [...] = shortestpath(..., 'Method', MethodValue, ...) [...] = shortestpath(..., 'Weights', WeightsValue, ...)

Аргументы

`BGObj`	Объект-биограф, созданный `biograph` (конструктор объекта).
`S`	Узел в графе, представленный матрицей близости N-на-N, извлеченной из объекта-биографа, `BGObj`.
`T`	Узел в графе, представленный матрицей близости N-на-N, извлеченной из объекта-биографа, `BGObj`.
`DirectedValue`	Свойство, указывающее, извлекается ли граф, представленный матрицей близости N-на-N из объекта-биографа, `BGObj`, направлена или не направлена. Войти `false` для неориентированного графа. Это приводит к игнорированию верхнего треугольника разреженной матрицы. По умолчанию: `true`.
`MethodValue`	Символьный вектор или строка, указывающая алгоритм, используемый для поиска кратчайшего пути. Возможны следующие варианты: `'Bellman-Ford'` - предполагает, что веса краев должны быть ненулевыми записями в матрице смежности N-на-N. Сложность времени `O(NE)`, где `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-by-N, извлеченной из объекта-биографа. `BGObj`. Он должен иметь одну запись для каждого ненулевого значения (края) в матрице смежности N-на-N. Порядок пользовательских весов в векторе должен соответствовать порядку ненулевых значений в матрице смежности N-на-N, когда она проходит по столбцам. Это свойство позволяет использовать веса с нулевым значением. По умолчанию `shortestpaths` получает информацию о весах из ненулевых записей в матрице смежности N-на-N.

Описание

Совет

Вводные сведения о функциях теории графов см. в разделе Функции теории графов.

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

[dist, path, pred] = shortestpath(BGObj, S, T) определяет кратчайший путь от одного источника до одного пункта назначения от узла 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] Дийкстра, Э. В. (1959). Заметка о двух задачах в соединении с графиками. Numerische Mathematik 1, 269-271.

[2] Беллман, Р. (1958). О проблеме маршрутизации. Ежеквартально прикладной математики 16 (1), 87-90.

[3] Сиек, Дж. Г., Ли, L-Q, и Люмсдейн, А. (2002). Руководство пользователя и справочное руководство библиотеки Boost Graph (Upper Saddle River, NJ: Pearson Education).

См. также

Темы

объект-биограф

Представлен в R2006b

Документация