Решите задачу кратчайшего пути в объекте биографика
[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 | Вектор символов, которая задает алгоритм, используемый для поиска кратчайшего пути. Варианты:
|
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 расстояния от источника до каждого узла (использование Infs для недоступных узлов и 0 для исходного узла). path содержит выигрышные пути к каждому узлу. pred содержит предшествующие узлы выигрышных путей.
[ определяет кратчайший путь от узла с одним источником-одним адресатом dist, path, pred] = shortestpath(BGObj, S, T)S к узлу T.
[...] = короткий путь (..., вызывает '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] Dijkstra, E.W. (1959). Примечание о двух задачах в соединении с графиками. Нумерише Математик 1, 269-271.
[2] Bellman, R. (1958). По проблеме маршрутизации. Ежеквартально по прикладной математике 16 (1), 87-90.
[3] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). Руководство пользователя библиотеки График (Upper Saddle River, NJ: Pearson Education).
allshortestpaths | biograph | conncomp | graphshortestpath | isdag | isomorphism | isspantree | maxflow | minspantree | topoorder | traverse