|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[166] Рис.25.4 НОВЫЙ: эскиз см. на полях книги Рис. 25.4 25.4. Плохой случай: релаксация ребра (u, v), где вершина и является потомком v в дереве предшествования. Если такое проивходит, возникает цикл, имеющий отрицательную сумму весов. что происходит с Gv при релаксации такого ребра (и, v). Поддерево с корнем в v отрезается (от прежнего родителя вершины v) и прививается к вершине и (tt[v] становится равным и). Это может нарушить структуру дерева только в том случае, если вершина и была потомком вершины v, то есть лежала в поддереве с корнем v (при этом образуется цикл, см. рис. 25.4) Нам остаётся убедиться, что такого произойти не может. Проверим, что в этом случае образующийся цикл (от v к и в дереве предшествования, а затем по ребру (и,v)) имеет отрицательную сумму весов. Поскольку ребро (и, v) подверглось релаксации, до её выполнения имело место неравенство d[u] + w(u,v) < d[v], или (d[u] - d[v]) + w(u, v) < 0. Мы сейчас покажем, что вес пути от v в и в графе Gv не превосходит d[u] - d[v], и тем самым найдём цикл отрицательного веса в графе G, достижимый из s, которого по предположению не существует. Итак, почему же вес пути в Gv от вершины v к вершине и не превосходит разницы значений функции d в конце и начале пути? Очевидно, достаточно проверить это для одного ребра, то есть проверить, что если ребро (p,q) в какой-то момент входит в Gv, то в этот момент то есть d[q] d\p] + w(p,q). Непосредственно после релаксации ребра (р, q) это неравенство обращается в равенство. Затем величины d\p] и d[q] могут уменьшаться. Если уменьшается d\p], то неравенство не нарушается. Если уменьшается d[q], это значит, что происходит релаксация ребра, ведущего в q, при этом меняется и ir[q] и для нового ребра (7r[g],g) выполнено неравенство (25.1). Это рассуждение завершает доказательство леммы 25.8 Пусть в результате последовательности релаксаций мы добились того, что d[v] = S(s,v) для всех вершин v. Покажем, что в этом случае граф Gv является деревом кратчайших путей. Лемма 25.9 Пусть G = (V, Е) - взвешенный ориентированный граф с весовой функцией w и исходной вершиной s, причем в графе G нет циклов отрицательного веса, достижимых из s. Предположим, что после операции lNlTlALlZE-SlNGLE-SouRCE(Gr, s), за которой следует некоторая последовательность релаксаций ребер, оказалось, что d[v] = S(s,v) для всех v £ V. Тогда подграф предшествования Gv является деревом кратчайших путей. w(p,q) d[q] - d[p] Доказательство Согласно определению, нам надо проверить, что [67-] совпадает со множеством вершин графа G, достижимых из s, что Gv - дерево с корнем s, и что пути в Gv из s в его вершины являются кратчайшими путями в G. Второе из этих утверждений есть лемма 25.8; из неё же следует, что все вершины Gv достижимы из s (даже в подграфе Gv); обратно, если вершина v ф s достижима в графе G из s, то d[v] = S(s, v) < оо, так что имела место релаксация ребра с концом v и ir[v] ф nil, то есть v £ [67-]. Этим доказано первое утверждение. Докажем третье утверждение. Неравенство (25.1) гарантирует, что длина пути от s до v в дереве Gv не превосходит d[v] - d[s] = d[v] = S(s, v), так что пусть этот - кратчайший. Упражнения 25.1-1 Укажите ещё два дерева кратчайших путей для графа рис. 25.2. 25-1.2 Приведите пример взвешенного ориентированного графа G = (V, Е) с исходной вершиной s, обладающего следующим свойством: для каждого ребра (и, v) £ Е существует как дерево кратчайших путей с корнем s, содержащее ребро (и, v), так и дерево кратчайших путей с корнем s, указанного ребра не содержащее. 25-1.3 Убедитесь, что доказательство леммы 25.3 проходит и для того случая, когда веса путей равны оо или -оо. 25-1.4 Пусть G = (V, Е) - взвешенный ориентированный граф с исходной вершиной s. Предположим, что после операции Initialize-Single-Source(G, s), за которой следует некоторая последовательность релаксаций ребер, оказалось, что ir[s] ф nil. Докажите, что G содержит цикл отрицательного веса. 25-1.5 Пусть G = (V, Е) - взвешенный ориентированный граф, в котором веса всех ребер неотрицательны. Выберем исходную вершину s £ V, а для каждой v £ V \ {s} выберем вершину ir[v] £ V таким образом, чтобы ir[v] была предшественником v на некотором кратчайшем пути из s в v; если v недостижима из s, положим tt[v] = nil. Приведите пример графа G и функции тг, удовлетворяющих приведенным выше условиям, для которых подграф Gv, построенный по функции тг, содержит циклы (в силу леммы 25.8, инициализация с последовательностью релаксаций такой функции 7г дать не может). 25-1.6 Пусть G = (V, Е) - взвешенный ориентированный граф с начальной вершиной s, не имеющий циклов отрицательного веса, достижимых из s. Покажите, что после операции Initialize-SlNGLE-SouRCE(Gr, s), за которой следует произвольная последовательность релаксаций рёбер, всякая вершина v £ [67-] достижима из s в графе Gv. 25-1.7 Пусть G = (V, Е) - взвешенный ориентированный граф Рис. 25.5 Рис. 25.5 Рис. 25.5. Алгоритм Дейкстры. Исходная вершина - крайняя левая. Оценки кратчайшего пути указаны в вершинах. Серым цветом выделены рёбра (u, v), для которых n[v] = и. Чёрные вершины лежат в множестве S, остальные находятся в очереди Q = V \ S. (а) Перед первой итерацией цикла while. Серая вершина имеет минимальное значение d и выбирается в качестве вершины и в строке 5 (б-е) Последовательные состояния после каждой итерации цикла while. Серая вершина выбирается в качестве вершины и при следующей итерации. Значения d и 7Г на рисунке (е) - окончательные. с начальной вершиной s, не содержащий циклов отрицательного веса. Покажите, что можно провести операцию Initialize-Single-Source, s), а затем \ V\ - 1 релаксаций ребер таким образом, что в результате равенство d[v] = S(s,v) будет выполняться для всех v е V. 25-1.8 Пусть G = (V, Е) - взвешенный ориентированный граф с начальной вершиной s. Предположим, что из вершины s достижим цикл отрицательного веса. Покажите, что существует бесконечная последовательность релаксаций, после каждой из которых функция d меняется. Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G = (V, Е) с исходной вершиной s, в котором веса всех ребер неотрицательны. (w(u, v) 0 для всех (и, и) £ Е). В этом разделе мы рассматриваем только такие графы. В процессе работы алгоритма Дейкстры поддерживается множество S С V, состоящее из вершин v, для которых S(s, v) уже найдено (то есть d[v] = S(s,v)). Алгоритм выбирает вершину и £V\S с наименьшим d[u], добавляет и к множеству S и производит релаксацию всех рёбер, выходящих из и, после чего цикл повторяется. Вершины, не лежащие в S, хранятся в очереди с приоритетами Q, определяемыми значениями функции d. Предполагается, что граф задан с помощью списков смежных вершин. Dijkstra(G,w,s) 1Initialize-Single-Source(G,s) 2S \gets \emptyset 3Q \gets V[G] 4while Q \ne \emptyset 5do u \gets Extract-Min(Q) 6S \gets S \cvrp \{u\> 7for (для) всех вершин v\in Adj[u] 8do Relax(u,v,w) Работа алгоритма Дейкстры показана на рис. 25.5. В строке 1 инициализируются d и тг, а в строках 2 и 3 инициализируются множество S (как пустое) и очередь Q = V \ S = V. При каждом исполнении цикла в строках 4-8 из очереди Q = V \ S изымается |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||