Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 21. Кратчайшие пути. описание и помогает в их понимании
|
|
| описание и помогает в их понимании. С точки зрения программиста важно обратить внимание, что мы можем реализовать каждый из этих алгоритмов, используя абстрактную операцию + (для вычисления веса пути на основе весов ребер) и абстрактную операцию < (для вычисления минимального значения на множестве весов пути), причем обе операции определяются исключительно в контексте операции ослабления (см. упражнения 19.55 и 19.56). Из свойства 21.1 следует, что кратчайший путь из s в t содержит кратчайшие пути из s в каждую другую вершину вдоль пути в /. Большинство алгоритмов поиска кратчайших путей также вычисляют кратчайшие пути из s в каждую вершину, которая находится ближе к s, чем к t (независимо от того, лежит ли вершина на пути из s в t), хотя это и не обязательно (см. упражнение 21.8). |
В терминах этих структур данных ослабление пути выражается следующим кодом:
if (d[s][t] > d[s][x] + d[x][t]) { d[s][t] = d[s][x] + d[x][t]; p[s][t] = p[s][x]; }
Подобно ослаблению ребра, этот код читается как другая формулировка данного нами неформального описания, так что в реализациях он используется непосредственно. Выражаясь более формально, ослабление пути отражает следующее.
Свойство 21.1. Если вершина х лежит на кратчайшем пути из s в t, то этот путь складывается из кратчайшего пути из s в х, за которым следует кратчайший путь из х в t.
Доказательство: Воспользуемся доказательством от противного. Иначе для построения более короткого пути из s в / мы могли бы воспользоваться любым более коротким путем из s в х или из х в t. ■
Мы сталкивались с операцией ослабления пути во время обсуждения алгоритмов транзитивного замыкания в разделе 19.3. Если веса ребер и путей либо равны 1, либо бесконечны (т.е. вес пути есть 1 только в том случае, если все ребра пути имеют вес 1), то ослабление пути суть операция, которая использовалась в алгоритме Уоршалла (если существуют пути из s в х и из х в t, то существует путь из s в t). Если мы определяем вес пути как число ребер на этом пути, то алгоритм Уоршалла обобщает алгоритм Флойда для нахождения всех кратчайших путей в невзвешенном орграфе; как будет показано в разделе 21.3, в дальнейшем это обобщается и применительно к сетям.
Важно обратить внимание, что с точки зрения математика все эти алгоритмы могут быть приведены к общему алгебраическому виду; это унифицирует их
РИСУНОК 21.7. ОСЛАБЛЕНИЕ ПУТИ
Эти схемы иллюстрируют операцию ослабления, на которой основаны наши алгоритмы кратчайших путей для всех пар. Мы отслеживаем лучший известный путь между всеми парами вершин и задаемся вопросом, является ли вершина i такой, что путь, проходящий через нее, явно лучше известного кратчайшего пути из s в t На верхнем примере это не так; на примере внизу ответ будет положительным. Каждый раз, когда мы встречаемся с некоторой вершиной i, причем такой, что длина известного кратчайшего пути из s в i плюс длина известного кратчайшего пути из i в t меньше длины известного кратчайшего пути из s в t, мы обновляем наши структуры данных, чтобы отметить, что в данный момент нам известен более короткий путь из s в t (в направлении от источника к i).
Часть 5. Алгоритмы на графах
РИСУНОК 21.8. ВСЕ КРАТЧАЙШИЕ ПУТИ
Две матрицы справа суть компактные представления всех кратчайших путей для типовой сети слева. Они содержат ту же информацию, что и список на рис. 21.3. Матрица расстояний слева содержит длину кратчайшего пути: элемент на пересечении строки s и столбца t есть длина кратчайшего пути из s в t. Матрица путей справа содержит информацию, необходимую для того, чтобы пройти по пути: элемент на пересечении строки s и столбца t есть следующая вершина на пути из s в t.
Решение задачи о кратчайших путях источник-сток с помощью такого алгоритма, когда t является наиболее удаленной от s вершиной, эквивалентно решению задачи о кратчайших путях из единственного источника для s И наоборот, мы могли бы воспользоваться решением задачи о кратчайших путях из единственного источника для s в качестве метода нахождения вершины, наиболее удаленной от s.
Матрица путей, которая используется в наших реализациях для задачи нахождения всех пар, является также представлением деревьев кратчайших путей для каждой вершины. Мы определили p[s][t] как вершину, которая следует за s на кратчайшем пути из s в tТаким образом, это то же, что и вершина, которая в обратной сети предшествует s на кратчайшем пути из / в s. Другими словами, столбец / в матрице путей сети суть индексированный вершиной вектор, который в обратном представлении задает SPT для вершины t. И наоборот, можно построить матрицу путей для сети за счет заполнения каждого столбца индексированным вершиной вектором SPT для соответствующей вершины в обратном представлении. Это соответствие проиллюстрировано на рис. 21.9.
В конечном итоге ослабление дает нам базовые абстрактные операции, которые необходимы для построения алгоритмов поиска кратчайших путей. Основная сложность связана с выбором, сохранять начальное или конечное ребро в кратчайшем пути. Например, алгоритмы для единственного источника более естественно выражаются при сохранении конечного ребра в пути так, что для реконструкции пути потребуется только один индексированный вершинами вектор, поскольку все пути ведут обратно к источнику. Этот выбор не представляет принципиальной трудности, поскольку можно либо использовать обратный граф как обычно, либо создать функции-элементы, которые скрывают это от клиентов. Например, можно было бы определить функцию-элемент в интерфейсной части, которая бы возвращала ребра кратчайшего пути в векторе (см. упражнения 21.15 и 21.16).
Глава 21, Кратчайшие пути
РИСУНОК 21.9.