В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 64
Текст из файла (страница 64)
Вычислитель- ные затраты максимальны, когда вершина 1 получает по- 345 стоянную метку последней и граф С является полным. В этом случае число итераций алгоритма равно ~С~ — 1, т. е. каждый из пп. 2 — 4 выполняется !С~ — 1 раз. Очевидно, что п. 4 выполняется за вромя 0(1), а для выполнения каждого из пп. 2, 3 достаточно времени О(!С!). 7'-б 5-5 д= дсд 7=7 д=д д=д г=г д=5 5 д=д д 7=г , г=д д-5 з д=д 7гд д=д 7=7 д=д г=г г=д д5 5 дьт Рнс. 70Л Построение пути с помощью меток 0 моя по осуществить, затратив не более 0(~6!) опораций.
Таким образом, в целом время построения кратчайп5его (5, д)-пути пе превосходят 0(~С)з). < 346 Пример 1. На рис. 76.1 изображены пять копий 6, (й = 1, 5) графа 6, каждая из которых отражает ситуацию, сложившуюся после очередной итерации алгоритма. Около каждой дуги написан ее вес. Вершинам копии Сз (Й = 1, 5) приписапы метки, полученные ими в резуль-~ тате выполнения первых я итераций. Некоторые дуги обведепы жирными линиями, т. е. отмечены. Добавление такой дуги (а, Ь) при переходе от С„к С„~~ означает, что вершила Ь получила свою метку 1(Ь) из а и эта метка стала постоянной на (к+1)-й итерации.
Вершина в нашем примере получает постояппую метку последней, и отмеченные дуги Сз образуют дерево кратчайших путей из ю При решепии мпогих задач возникает необходимость отыскапия в кевзвешепном графе (г, 1)-пути с минимальяым количеством дуг. Такой путь, очевидно, можно яайти с помощью алгоритма Дийкстры. Для этого достаточно присвоить всем дугам графа 6 веса, равпые 1, и применить алгоритм Фз. Проследим работу алгоритма в этой ситуации, обращая особое внимание па последовательпость, в которой вершины графа С получают постоянные метки. Очевидно, что вначале постоянные метки 1= 1 получат все вершины мпожества Г(з).
Затем метка 1=2 будет присвоена концам дуг, выходящих из Г(з). Вообще, постоянную метку 1=Й получают еще пе помеченные вершины, являющиеся концами дуг, исходящих из вершин с метками (= и — 1. Этот процесс обхода (и присвоения меток) воршип графа называют поиском в ширияу в графе (па интуитивном уровпе поиск в ширину описан в з 9). По окончании поиска в ширину метка ((х) вершины х раева минимальному числу дуг в (з, х)- пути. Как и ранее, сам этот путь определяется метками О. Осуществление поиска в ширину с помощью алгоритма Дийкстры связано, как мы зпаем, с вычислительными затратами 0(~С~э). Рассмотрим алгоритм .Фв, осуществляющий поиск в ширину за время 0(~ЕС~).
В этом алгоритме метки 1 и 0 играют ту же роль, что и в предыдущем, с той, однако, разпицей, что метки ( пе делятся па временные и постоянные. Как только вершина х получает метку ((х)ть, эта метка сразу становятся постоянной (т. е. окопчательной). За счет этого, в частности, достигается экономия времени вычислений по сравнению с алгоритмом Дийкстры. Особую роль в алгоритме .Фг играет список ф. Каждая вершина графа один раз заносится в этот список и один раз из него вычеркивается. При этом вычеркивается все время первая (па данный момент) вершина этого списка, а только что добавленная вершина всегда является последней в списке, т. е.
~ — очередь. Вначале в (т' находится единственная вершина г, 1(г) = О, а все остальные вершины меток не имеют. Общая итерация состоит в следующем. Выбирается первая вершина х в списке 1т. Каждой непомеченной вершине ужГ(х) присваиваются метки 1(у) =1(х)+ 1 и 0(у)=х, после чего вершина у становится последней в списке ф, а вершина х удаляется из ф. Алгоритм прекращает работу, как только в (т' не останется ни одной вершины.
При этом вершины, достижимые из г, будут иметь метки, а недостижимые — нет. Для быстрого выполнения операций вычеркивания и включения элементов в О используются переменные указатели р и д — адреса первой и последней занятых ячеек списка (т соответственно. Будем считать, что граф С задан списками смежности и Ж, — список, содержащий концы всех дуг, исходящих из вершины о.
Алгоритм,Мв поиска в ширину. 1. (~(1):= г, р:= 1, д:= 1, 1(г):= О. 2. х:= ~7(р), пг:= 1Г(х)! (выбрана первая вершина х очереди Я . (Пп. 3 — 5 — присвоение меток непомеченным вершинам из Г(х)]. 3, й:=1. 4. Если вершияа у=А'„(й) имеет метку, то перейти к п.
5. Иначе 1(у):=1(х)+ 1, 0(у):= х, д:= д+ 1, (т(д):= у (вершина у помечена и включена в очередь Я и перейти к п. 5. 5. Если й = и, то перейти к п. 6, иначе й:= й+ 1 и перейти к п. 4. 6. р:= р+ 1 (вершина х исключена из Я. 7. Если р) д, то конец (Ч=~, т. е. все вершины, достижимые из г, получили метки), иначе перейти к п. 2. У т в е р ж д е н и е 76.2. Алгоритм,Фв присваивает метки 1 и 0 всем вершинам графа, достолсимым иэ вершины г эа время 0(!ЕС~). Лрп этом (г, ..., Ог(х), 0'(х), 0(х), х) — (г, х)-путь с минимальным числом дуе, а 1(х) — число дуэ в этом пути. ~' Основные вычислительные затраты связаны с выполнением п.
3 алгоритма. Суммарное время выполнения 348 этого пункта составляет 0 ( ~ ) Ж )) = 0((ЕС ~), по- ~ иго скольку каждый из списков Ж„просматривается в точности один раз. Затраты па выполнение других пунктов, очевидно, не превосходят этой величины. Бэппе отмечалось, что результаты алгоритма Фз (т. е. метки 1 и О) те же, что и в алгоритме Дийкстры, если каждой дуге графа 6 приписать вес, равный 1. Поэтому справедливость второго утверждения следует нз утверждения 76.1. <з 3 а м е ч а н и е 4. Иногда требуется искать пути из вершин множества Х~ г'6 во все остальные вергпнны. Для решения этой задачи достаточно слегка модифицировать алгоритм Фз, изменив в нем п.
1. Именно, в список 0 следует поместить все вершины множества Х и положить 1(х) = О для каждой вершины хее Х. На модифицированный таким образом алгоритм .Фз будем ссылаться как па поиск в ширину из множества Х. Перейдем теперь к рассмотрению общей ситуации. Будем считать, что в графе 6 допускаются дуги отрицательного веса. Предлагаемый ниже алгоритм .М7 строит в таком графе кратчайшие пути между всеми парами вершин графа при условии, что в графе нет отрицательных контуров (контуров отрицательного веса).
Если же такой контур в графе имеется, то алгоритм сообщает об этом и прекращает работу, оставляя задачу отыскания кратчайшего пути перешешшй (см. ниже замечание 6). Будем считать, что граф С, ~6~ =и, задан матрицей весов И'=1И'вз, т. е. И'и=и~(1, 1), если (1, 1)~ЛС, и И'в= в противном случае. Кроме того, полагаем И'э= О для всех 1=1, 2, ..., и. Алгоритм основан на следующих соображениях. Пусть 1, у, й — три любые вершипы графа С, и мы хотим получить (1, 1)-путь, кратчайший среди (1, 1')-путей, пе содержащих внутренних вершин, отличных от й. Очевидно, что для этого достаточно выбрать меньшую из двух величин И'е и И'„+ + Ип, которая и будет весом такого (1, 1)-пути. Если зафиксировать й и проделать эту операцию (назовем ее 1-операиией, примененной к индексу й) для всех пар (1, 1), то получим матрицу И" =1И'О1, у которой И'ц = ппп(И'ц, И'за + И'хп) Оказывается (это будет позднее доказано), имея матрицу И" весов кратчайших путей, проходящих только через вершины мпоязества Я = 'г'6, можно получить такую яге матрицу для путей, проходящих через множество Я О (т), т Ф Я.
Для этого доста- 349 точно применить 1-операцию к индексу лг н всем элементам матрицы И". Именно в этом и состоит итерация алгоритма,Фн который, начиная с И'з = И', строит такую последовательность матриц И'з, И', ..., И'", что И™ получается из И' ' применением т-операции к индексу т и матрице И' '. Если в графе 6 нет отрицательных контуров, то элемент И';; матрицы И™ при каждом т равен весу кратчайшего (г, 1)-пути, все впутренпие вершины которого принадлежат множеству (1, 2, ..., т). Таким образом, последняя из этих матриц, И'", содержит веса кратчайших путей между всеми парами вершин графа. Для того чтобы после окончания работы алгоритма иметь возмонсность быстро найти кратчайший путь между любой парой вершин, будем на к-й итерации вместе с матрицей $Р строить матрицу Р~ =1Р~;1 Вначале полагаем Р;; = 1(1,у = 1, п). Далее, на й-й итерации по- Й Й вЂ” 1 лб Й вЂ” 1 И'ц = И'о, ~+ И'ц, ~.
Таким образом, Р~; — номер вершины, предшествующей вершине 1 в текущем (ю', 1)-пути, т. е. в кратчайшем (1, 1)-пути, все внутренние вершины которого содержатся в множестве (1, 2, ..., л). Матрица Р =1Рн~~ играет ту же роль, что и метки О в предыдущих алгоритмах ззз и .Фз. С помощью этой матрицы кратчайший (1, 1)-путь Л(1, 1) определяется следующим образом: Л(1, 1)=(1, ..., Ь, (н (п 1), где )', = Рй, в, а )2 мг> Уз ны Алгоритм .Фт отыскания кратчайших путей между всеми парами вершин.
1. И":= Иг, й:=1, Р:='~)Р',;~(, где Р';; =1, если И"О~ со, и Р;; = О в противном случае. 2. Выполнить для всех 1, у=1, гы если И'е, '(И'"";ь '+ + И~а,", Р,:= Рьг'. 3. Если для некоторого 1, 1 ~1( п, И'ц< О, то конец [в графе имеется отрицательный контур). Иначе перейти к п. 4. 4, й:= й + 1. Если к = п + 1, то конец ~И'" = 1 И'ч'1— матрица весов кратчайших путей, определяемых с помощью матрицы Р =1Р;;Ц. 3 а м е ч а н и е 5. Алгоритм будет применим к смешанным графам, если каждое неориептированное ребро заменить на две дуги того же веса (см. замечание 2).
350 При этом следует учесть, что неориентированное ребро отрицательного веса сразу приводит к отрицательному контуру. 3 а м е ч а к и е 6. Алгоритм «отказывается» строить кратчайшие пути, когда в графе 6 имеются отрицательные контуры. Б этом случае задача отыскания кратчайшего пути между двумя вершинами (или между всеми парами вершин) остается корректной, но становится очень трудной.
Можно показать, что она не менее трудна, чем, например, задача о коммивояжере. Переидом теперь к обоснованию алгоритма мР» и оценке его трудоемкости. Утверждение 76.3. Пусть взвешенный ориентированный мультиграф Л имеет зйлерову цепь, соединяю»цую вершины а и Ь. Если в Л нет отрицательных контуров, то в нем имеется такой (а, Ь)-путь Р, что ш(Л)~ ш(Р).
> Будем считать, что мультиграф Л не является путем (иначе утверждение тривиально). Поэтому он содержит некоторый контур Я. Удалив из Ь все дуги этого контура, получим мультиграф Е. Поскольку ш(Я)~0, то ш(А)> ш(Л'). Кроме того, согласно теореме 65.2 полустепени вершин мультиграфа Л' удовлетворяют соотношениям г)"(а) = а' (а) + 1, а (Ь) = й+(Ь) + 1, а+ (о) = и (о), о Ф а, Ь.
Поэтому вершины а и Ь принадлежат одной его слабой компоненте Е", и последняя содержит эйлерову (а, Ь)-цепь. Продолжая подобным образом, получим требуемый (а, Ь)-путь. 4 Утверждение 76.4. Если в графе нет отрицательных контуров, то при всех к, », 1= 1, и Итп — вес кратчайшего (~, 1)-пути, все внутренние вершины которого содержатся в множестве (1, 2, ..., (г).
> Доказываем индукцией по к. При )г = 1 справедливость утвер»кдения очевидна. Предположим, что оно справедливо для 2, 3, ..., й — 1, и рассмотрим Иф. Пусть Р' — кратчайший (», 1)-пут»и все внутренние вершины которого принадлежат множеству (1, 2, ..., к). Если Р» не включает вершину к, то И'я = И'0 н, согласно предположению индукции, ш(Р') = И'ц = И'и. Допустим теперь, что Р» содержит вершину к. Обозначим через Р~ 351 и Рг части пути Рг от 1 до й и от й до 7 соответственно. Предположим, что один из этих путей, например Раен пе является кратчайшим, и пусть Р— кратчайший (1, к)-путь, все вершины которого содержатся в множестве (1, 2, ..., (г — 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
