Алгоритмы - построение и анализ (1021735), страница 143
Текст из файла (страница 143)
Если после этого значение И [о; г] изменяется, то оно может только уменьшаться. Поэтому непосредственно перед вызовом процедуры КБ.АХ(оь г, оь, и) выполняется неравенство г1[о;] > д[ог т]+ш(сч ыо;) для всех г = 1,2,...,Й вЂ” 1. (24.12) Поскольку величина тг [пь] в результате вызова изменяется, непосредственно перед этим выполняется строгое неравенство 1[оь] > 1[оь-г]+го(оь-ыоь).
Суммируя это строгое неравенство с 1с — 1 неравенствами (24.12), получим сумму оценок кратчайшего пути вдоль цикла с: ь ь ~~г г([ог] > ~~ (г([тг з]+ю(ег ыо;)) = г=1 г=1 и [ог-1] + „,~ то (ог-1, %) г=1 Однако ~~> г([сч] = ~~> И [сч з], поскольку каждая вершина цикла с входит в каждую сумму ровно по одному разу.
Из этого равенства следует 0 > ~ ы (иг ы о;). Таким образом, суммарный вес цикла с — величина отрицательная, что и приводит к желаемому противоречию. Глава 24. Кратчайшие пути нз одной вершины 699 Рис. 24.9. Иллюстрация того, что путь в графе С из истока з в вершину с — единственный Итак, доказано, что ф— ориентированный ациклический граф. Чтобы показать, что он образует корневое дерево с корнем в, осталось доказать (см.
упражнение Б.5-2), что для каждой вершины с Е 'г' в графе С имеется единственный путь из истока а в вершину гг. Сначала необходимо показать, что из истока з существует путь в каждую вершину множества Ъ'„. В это множество входят вершины, значение атрибута я которых отлично от значения гчгг., а также вершина ж Идея заключается в том, чтобы доказать наличие такого пути из истока з в каждую вершину множества У„ по индукции. Детали предлагается рассмотреть в упражнении 24.5-6.
Чтобы завершить доказательство леммы, теперь нужно показать, что для любой вершины гг е У в графе С существует не более одного пути из вершины з в вершину гг. Предположим обратное. Другими словами, предположим, что из истока а существует два простых пути в некоторую вершину тл путь рг, который можно разложить как в - и - к -~ я - и, и путь рз, который можно разложить как а - и - у -~ к - с, где х ф у (рис.
24.9). Однако в таком случае выполняются равенства к [л] = х и гг [з] = у, откуда следует противоречие х = р. Приходим к выводу, что в графе С существует единственный путь из истока а в вершину с, и, следовательно, этот граф образует корневое дерево с корнем в. П Теперь можно показать, что если после некоторой последовательности этапов ослабления всем вершинам присвоены истинные веса кратчайших путей, то подграф предшествования Ск — это дерево кратчайших путей. Лемма 24.17 (Свойство подграфа предшествования). Пусть С = (1г, Е) — взвешенный ориентированный граф с весовой функцией гс: Š— В,, а в е 1' — исток.
Предположим также, что граф С не содержит циклов с отрицательным весом, достижимых из вершины ж Вызовем процедуру 1гчгтглг.гамп Бггчпье БОиксе(С, в), после чего выполним произвольную последовательность шагов ослабления ребер графа С, в результате которой для всех вершин с б У выполняется равенство г1(о] = б (а, о). Тогда подграф предшествования С вЂ” дерево кратчайших путей с корнем в. Доказаглельстао.
Необходимо доказать, что для графа С„выполняются все три свойства, сформулированные в разделе "Представление кратчайших путей" для Часть Ч1. Алгоритмы для работы с графами 700 деревьев кратчайших путей. Чтобы доказать первое свойство, необходимо показать, что К, — множество вершин, достижимых из истока а По определению вес кратчайшего пути б (в, о) выражается конечной величиной тогда и только тогда, когда вершина о достижима из истока в, поэтому из истока з достижимы только те вершины, юторым соответствуют юнечные значения Н.
Однако величине И [о], соответствующей вершине о е 1' — [з), конечное значение присваивается тогда и толью тогда, когда тг [о] ф мп.. Таким образом, в множество Ъ'„входят только те вершины, юторые достижимы из истока ж Второе свойство следует непосредственно из леммы 24.16. Поэтому остается доказать справедливость последнего свойства для дерева кратчайших путей: для каждой вершины о Е У единственный простой путь з - о в графе С вЂ” это кратчайший путь в графе С из истока в в вершину о.
Пусть р = (ос,оы...,оь), где ос = з и оь = о. При г = 1,2,..., к выполняются соотношения д [о;] = б (в, о;) и д [о;] > с1 [о; 1] + ю (о; ы о;), из чего следует, что ю(о; ыо,) < б(з,о;) — б(з,о; 1). В результате суммирования весов вдоль пути р получаем ь ю(р) = ~~ ю(о; но;) < 1=1 ь < ,'~ (б (в, о;) — б (з, о; 1)) = 1=1 = б (в > оь) — б (з, оо) = = б(в,оь), где предпоследнее равенство следует из "телесюпичности*' суммы разностей, а последнее — из того, что б(з, ос) = б (в,з) = О.
Таким образом, справедливо неравенство ю (р) < б (з, оь). Поскольку б(в, оь) — нижняя граница веса, которым обладает любой путь из истока з в вершину оы приходим к выводу, что ю(р) = б(з, оь), и поэтому р — кратчайший путь из истока в в вершину о = оь. И Упражнения 24.5-1. Для ориентированного графа, изображенного на рис. 24.2, приведите пример двух деревьев кратчайших путей, отличных от показанных. 24.5-2. Приведите пример взвешенного ориентированного графа С = (КЕ) с весовой функцией ю: Š— К и истоком в, для которого выполняется сформулированное ниже свойство: для каждого ребра (и, о) Е Е существует дерево кратчайших путей с корнем з, содержащее ребро (и, о), Глава 24.
Кратчайшие пути из одной вершины 701 и другое дерево кратчайших путей с корнем я, в котором это ребро от- сутствует. 24.5-4. Пусть С = (У,Е) — взвешенный ориентированный граф с исходной вершиной з, инициализированный процедурой 1ы1т~лшгк Япчсье 801/псе(С, з). Докажите, что если в результате выполнения последовательности этапов ослабления атрибуту к [а[ присваивается значение, отличное от мп., то граф С содержит цикл с отрицательным весом. 24.5-5. Пусть С = (У, Е) — взвешенный ориентированный граф, не содержащий ребер с отрицательным весом, и пусть в е Ъ" — исток. Предположим, что в качестве к [о[ может выступать предшественник вершины е на любом кратчайшем пути к вершине и из истока а, если вершина е Е Ъ' — (а) достижима нз вершины в; в противном случае я [е[ принимает значение ыи..
Приведите пример такого графа С и значений, которые следует присвоить атрибутам к [е], чтобы в графе С образовался цикл. (Согласно лемме 24.1б, такое присвоение не может быть получено в результате последовательности этапов ослабления.) Пусть С = (1г, Е) — взвешенный ориентированный граф с весовой функ- 24.5-6.
цией и: Š— ~ Н,, не содержащий циклов с отрицательным весом. Пусть ле Ъ" — исток, а граф С инициализируется процедурой 1ьлтышге Б лчсье Яоцксе(С, а). Докажите, что для каждой вершины и е $' в графе С существует путь из вершины в в вершину о и что это свойство поддерживается как инвариант в ходе произвольной последовательности ослаблений. Пусть С = (Ъ; Е) — взвешенный ориентированный граф, не содержащий циклов с отрицательным весом.
Пусть также з е Р— исток, а граф С инициализируется процедурой 1мт1лшгп Бпчаьп Бо~жся(С, л). Докажите, что существует такая последовательность [Ц вЂ” 1 этапов ослабления, что для всех вершин е Е Ъ' выполняется равенство Н [е[ = Б (а, о). Пусть С вЂ” произвольный взвешенный ориентированный граф, который содержит цикл с отрицательным весом, достижимый из истока л.
Покажите, что всегда можно построить такую бесконечную последовательность этапов ослабления ребер графа С, что каждое ослабление будет приводить к изменению оценки кратчайшего пути. 24.5-7. 24.5-8. 24.5-3. Усовершенствуйте доказательство леммы 24.10, чтобы она охватывала случаи, когда веса кратчайших путей равны оо и — оо. 702 Часть ЧБ Алгоритмы для работы с графами Задачи 24-1. Улучшение Йена алгоритма Беллмана-Форда Предположим, что в каждом проходе алгоритма Беллмана-Форда ослабления ребер упорядочены следующим образом. Перед первым проходом вершины входного графа С = (У, Е) выстраиваются в произвольном порядке сы сз,..., ху~.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
