Graph
::shortestPathAllPairs
Кратчайшие пути от и до всех вершин
Блокноты MuPAD® будут демонтированы в будущем релизе. Используйте live скрипты MATLAB® вместо этого.
Live скрипты MATLAB поддерживают большую часть функциональности MuPAD, хотя существуют некоторые различия. Для получения дополнительной информации смотрите, Преобразуют Notebook MuPAD в Live скрипты MATLAB.
Graph::shortestPathAllPairs(G
, <SearchFor = Weights | Costs
>)
Graph::shortestPathAllPairs(G)
возвращает таблицу со всеми путями между всеми вершинами.
Graph::shortestPathAllPairs(G, SearchFor=Costs)
возвращает table
со всеми путями согласно затратам ребра.
Graph::shortestPathAllPairs(G, SearchFor=Weights)
возвращает table
со всеми путями согласно весу ребра. (Значение по умолчанию)
Маленький график, который будет использоваться в алгоритмах:
G := Graph([a, b, c, d], [[a, b], [a, c], [b, c], [c, d]], EdgeWeights = [2, 1, 3, 2], EdgeCosts = [1, 3,1, 2], Directed):
Теперь кратчайший путь между всеми вершинами найден согласно весу ребра, потому что никакая спецификация не была дана, и значения по умолчанию используются.
Graph::shortestPathAllPairs(G)
Интерпретация таблицы следующие:
Первая таблица содержит каждый путь: (FromVertex, ToVertex) = вес/стоимость. Вторая таблица немного более хитра. Левая сторона снова является самим путем. На правой стороне, хотя, вершина, которая была найдена перед итоговой вершиной, была достигнута, утверждается. Если, например, путь от a
к d
должен быть найден со всеми вершинами, которые используются в этом пути, он сделан следующим образом: Сначала возьмите сам путь (a, d)
. Предшественником является c
. Теперь взгляните для пути (a, c)
. Это - предшественник, a
. Поскольку предшественник равняется первой вершине в пути, который будет найден, поиск закончен и путь a -> c -> d
найден. Искать график затраты опция SearchFor=Costs
должен быть добавлен.
Graph::shortestPathAllPairs(G, SearchFor = Costs)
Теперь веса графика изменяются, так, чтобы был присвоен отрицательный вес ребра. Вы будете видеть, что это не влияет на правильность результатов, которые алгоритм возвращает (как, например, Дейкстра).
G := Graph([a, b, c, d], [[a, b], [a, c], [b, c], [c, d]], EdgeWeights = [2, 1, 3, 2], EdgeCosts = [1, 3,1, 2], Directed):
G := Graph::setEdgeWeights(G, Graph::getEdges(G), [2, 1, -3, 2]):
Graph::shortestPathAllPairs(G)
|
График |
|
Задает, рассматриваются ли веса графика или затраты. Значением по умолчанию является |
Перечислите состоящий из двух таблиц. Первая таблица содержит сумму весов пути или затраты и второе предшественники для каждого пути (чтобы найти полный путь).
Алгоритм также известен как алгоритм Роя-Вошола или Флойда-Вошола. Идея позади него состоит в том, чтобы решить задачу непрерывным умножением матриц. он, который единственная разница - то, что Флойд использует присвоение a i, j: = min (a i, j, a i, k + a k, j).
[1] Ahuja, Magnanti, Orlin: сетевые потоки, Prentice Hall, 1 993 раздела 5.6