Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Часть 5. Алгоритмы на графах. продвижения от вершины к вершине, мы будем придерживаться тех же соглашений, которые учитывались в других алгоритмах поиска на графе в главах 18-20: мы
|
|
| продвижения от вершины к вершине, мы будем придерживаться тех же соглашений, которые учитывались в других алгоритмах поиска на графе в главах 18-20: мы используем индексированный вершиной вектор spt для записи последнего ребра на кратчайшем пути из источника в данную индексированную вершину. Эти ребра составляют дерево. В случае применения таких структур данных реализация ослабления ребра является простой задачей. При поиске кратчайших путей для единственного источника мы используем следующий код, чтобы произвести ослабление вдоль ребра е, направленного от v к w: if (wt[w] > wt[v] + e-> wt()) { wt[w] = wt[v] + e-> wt(); spt[w] = e; } Этот фрагмент кода и прост, и выразителен; вместо определения ослабления как высокоуровневой абстрактной операции, мы включаем в наши реализации приведенный выше код без каких-либо изменений. |
■ Ослабление ребра. Проверка, дает ли продвижение
вдоль данного ребра новый кратчайший путь к
вершине назначения.
■ Ослабление пути. Проверка, дает ли прохождение
через данную вершину новый кратчайший путь,
соединяющий две других заданных вершины.
Ослабление ребра есть частный случай ослабления пути; тем не менее, мы рассматриваем оба случая как отдельные операции, поскольку используем их порознь (в одном случае это алгоритмы для единственного источника, во втором — алгоритмы для всех пар). В обоих случаях главное требование, которое мы предъявляем к структурам данных, используемым для представления текущего состояния знаний о кратчайших путях сети, состоит в том, что мы должны иметь возможность обновить их, чтобы можно было легко отобразить изменения, связанные с операцией ослабления.
Прежде всего, рассмотрим ослабление ребра, которое иллюстрируется на рис. 21.5. Все рассматриваемые алгоритмы поиска кратчайших путей для единственного источника базируются на таком шаге: приводит ли нас данное ребро к рассмотрению более короткого пути из источника к адресату?
Структуры данных, необходимые для поддержания этих действий, просты. Во-первых, наша основная задача состоит в том, чтобы вычислить длины кратчайших путей из источника в каждую из прочих вершин. Условимся сохранять длины известных кратчайших путей из источника в каждую из вершин в индексированном вершинами векторе wt. Во-вторых, для записи самого пути
РИСУНОК 21.5. ОСЛАБЛЕНИЕ РЕБРА
Эти диаграммы иллюстрируют операцию ослабления, на которой основываются наши алгоритмы поиска кратчайших путей для единственного источника. Мы прослеживаем известные кратчайшие пути из источника s в каждую вершину и задаемся вопросом, лежит ли ребро v-w на более коротком пути в w. На верхнем примере это не выполняется; это значит, что мы должны его (ребро) отвергнуть. На нижнем примере это выполняется; значит, мы должны обновить наши структуры данных, чтобы указать, что лучший известный путь достижения w из s проходит через v, поэтому и принимается v-w.