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 со всеми путями согласно весу ребра. (Значение по умолчанию)

Примеры

Пример 1

Маленький график, который будет использоваться в алгоритмах:

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)

Пример 2

Теперь веса графика изменяются, так, чтобы был присвоен отрицательный вес ребра. Вы будете видеть, что это не влияет на правильность результатов, которые алгоритм возвращает (как, например, Дейкстра).

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)

Параметры

G

График

Опции

SearchFor

Задает, рассматриваются ли веса графика или затраты. Значением по умолчанию является Weights.

Возвращаемые значения

Перечислите состоящий из двух таблиц. Первая таблица содержит сумму весов пути или затраты и второе предшественники для каждого пути (чтобы найти полный путь).

Алгоритмы

Алгоритм также известен как алгоритм Роя-Вошола или Флойда-Вошола. Идея позади него состоит в том, чтобы решить задачу непрерывным умножением матриц. он, который единственная разница - то, что Флойд использует присвоение a i, j: = min (a i, j, a i, k + a k, j).

Ссылки

[1] Ahuja, Magnanti, Orlin: сетевые потоки, Prentice Hall, 1 993 раздела 5.6

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