В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 63
Текст из файла (страница 63)
8 множество Е, является множеством минимальных по весу ребер для леса Т, рассматриваемого в этот момент. Поэтому согласно утверждению 75.2 граф Т'= = Т+Е1 снова является остовным лесом. Это означает, г а, г а, г а, а 4 д Ряс. 75.2 и, ус . а.иО а а~ и, иг а,=~а и,,~ Рзс. 75.3 что алгоритм строит некоторый остов графа С. Минималь- ность этого остова доказывается с помощью теоремы75.1 точно так же, как при обосновании предыдущего алгоритма. 34$ Выясним теперь быстродействие алгоритма Ф4. Для однократного выполнения каждого из пп. 3 — 6 достаточно времени 0(1) и, следовательно, построение Е~ осуществляется за время 0(~ЕС~). Таких же затрат достаточно и для однократного выполнения пп.
8 — 11. Таким образом, затраты на переход от Т к Т' = Т+ Е~ (т. е. на выполнение одной итерации) составляют О(!ЕС~) операций. Оценим теперь число итераций алгоритма. Поскольку одно ребро может быть минимальным по весу не более чем для двух компонент леса Т, то на каждой итерации!Е~! ~ р(Т)/2.А так как Т+Е~ — лес,тор(Т+Е~)( < р(Т)72, т. е.
на каждой итерации число компонент уменьшается по крайней мере вдвое. Это означает, что число итераций алгоритма не превосходит 1ол 1С!, следовательно, он строит минимальный остов за время О(!ЕС! 1ол!С!). <3 Пример 2. Применим алгоритм .Ф4 к графу, изображенному на рис. 75.2. На первой итерации будет найдено множество Е~ = (а)аг, а~аз, ашп агав, авар, адам) минимальных по весу ребер для леса, имеющего одповершинные компоненты. Остовпые леса, полученные в результате выполнения 1-й, 2-й и 3-й итераций, изображены на рис.
75.3. Последний из пих является минимальным остовом. э 76. Кратчайшие пути Пусть С =(У, А) — ориентированный взвешенный граф. Задача о кратчайшем пути состоит в отыскании пути минимального веса, соединяющего заданные начальную и конечную вершины графа С при условии, что хотя бы один такой путь существует. Начальную н конечную вершины обозначим соответственно через з и ~; (з, 1)-путь минимального веса будем называть кратчайпгим (з, 1)-путем. Вначале рассмотрим случай, когда веса всех дуг графа неотрицательпы, т. е. ю(е) > 0 для каждой дуги е ~н А.
В этом случае решение задачи о кратчайгпем пути является существенно менее трудоемким, чем в общем случае. Первый эффективный алгоритм построения кратчайшего пути в графе с неотрицательными весами дуг предложил Е. Дийкстра в 1959 г. На каждой итерации этого алгоритма всякая вершина в графа С имеет метку 1(в), которая может быть постоянной либо временной. В первом случае 1(и)- вес крат- 342 чайшего (г, и)-пути.
Если же метка ((г) временная, то 1(и) — вес кратчайшего (г, о)-пути, проходящего только через вершины с постоянными метками. Таким образом, временная метка 1(и) является оценкой сверху для веса кратчайшего (г, и)-пути, н став на некоторой итерации постоянной, она остается такой до конца работы алгоритма. Кроме 1(и), с каждой вершиной и графа 6, за исключением г, связывается еще одна метка — 0(и).
На ка»идой итерации 0(и) является номером вершины, предшествующей и в (г, о)-пути, имеющем минимальный вес среди всех (г, и)-путей, проходящих через вершины, получившие к данному моменту постоянные метки. После того как вершина 1 получила постоянную метку, с помощью меток 0(с) легко указать последовательность вершин, составляющих кратчайший (г, С)-путь. Перед началом первой итерации алгоритма вершина г имеет постоянную метку 1(г) = О, а метки ~ всех остальных вершин равны со и эти метки временные. Общая итерация алгоритма состоит в следующем. Пусть р— вершина, получившая постоянную метку 1(р) на предыдущей итерации. Просматриваем все вершины и ш Г(р), имеющие временные метки, с целью уменьшения (если это возможно) этих меток. Метка ((и) вершины и ~ Г(р) заменяется на 1(р)+ ш(р, и), если оказалось, что 1(и)~ ) ((р)+ и~(р, о).
В этом случае говорим, что вершина г получила свою метку ( из вершины р, и полагаем 0(и)= = р. Если же Цп)~ 1(р)+ ы(р, и), то метки 0 и 1 вершины и не изменяются на данной итерации. Алгоритм заканчивает работу, когда метка ((~) становится постоянной. Как уяге говорилось выше, 1(8) — вес кратчайшего (г, ~) -пути, который будем обозначать через Рз. Этот путь определяется с помощью меток 0 так: Р =(г, ..., Вз(ю), 0'р), 0(~), г), где О» = 0 (О (...
0 (о)...)) для любой вершины и ~ УС. » гав Будем считать, что граф С задан матрицей весов либо списками смежности. Алгоритм Фз Дийкстры поиска кратчайшего пути. 1. Положить 1(г):=О и считать эту метку постоянной. Положить ((с):= для всех о ~ 'г'С, и Ф г, и считать эти метки временными. Положить р:= г. 2. Для всех и ~н Г(р) с временными метками выполнить: если 1(и) ~ 1(р)+ ш(р, о), то Цр):= 1(р)+ ю(р, и) и 0(о): р. Иначе 1(и) и 0(и) не менять. 333 3. Пусть У' — множество вершин с временными метками й Найти вершину ее, такую что ((е») = ппп ((и).
гию Считать метку ((е*) постоянной меткой вершины ее. 4. р:=ее. Если р=г, то перейти к п. 5 Р(г) — вес кратчайшего пути) . Иначе перейти к п. 2. 5. Рг:=(г, ..., 0»(Г), 0'(~), О(~), г) (Р* — кратчайший путь). Конец. Прежде чем перейти к обоснованию алгоритма, сделаем три полезных замечания. 3 а м е ч а п и е 1.
Как легко видеть, алгоритм,Фг применим к смешанным и, в частности, к неориентированпым графам. Для этого достаточно каждое неориентированное ребро ие графа, имеющее вес ю(и, и), рассматривать как пару дуг (и, е) и (е, и) того же веса. Замечание 2. Если п. 4 модифицировать так, чтобы алгоритм заканчивал работу только после получения всеми вершинами постоянных меток, то он будет строить кратчайшие пути из г в каждую из остальных вершин.
Если к тому же вместе с превращением метни вершины е* в постоянную (п. 3 алгоритма) заносить дугу (0(е*), е*) в множество А*, то после окончания работы алгоритма граф П =(УС, Ае) будет корневым ориентированным остовным деревом. Это дерево называют деревом кратчайших путей из г графа С. Для любой вершины е~и УС единственный (г, е)-путь в дереве .0 является кратчайшим (г, и)-путем в графе С. 3 а м е ч а н и е 3.
Алгоритм Фг, модифицированный так, как указано в замечании 2, можно рассматривать как алгоритм построения дерева П кратчайших путей из вершины г графа С. О этой точки зрения алгоритм .Фг аналогичен алгоритму г»» построения минимального остова.
Действительно, построение дерева П состоит в последовательном увеличении уже построенного фрагмента путем добавления некоторой дуги, «выходящей» из этого фрагмента. При этом метки 1 и О играют такую же роль, как и метки а и 0 в алгоритме «»г. У т в е р ж д е н и е 76А.
Алгоритм,Ф» строит в графе С кратчайший (г, г)-путь га время О(!С!«). > Заметим вначале, что метка вершины е (((е)Ф ) равна весу (г, е)-пути, который построен алгоритмом к этому моменту. Он определяется метками О, имеющимися на заданный момент. Поэтому для доказательства опти- мальности (г, 1)-пути, соответствующего постояннои метке 1(1), достаточно доказать, что постоянная метка 1(э) каждой вершины и равна весу кратчайшего (г, э)-пути. Это утверждение будем доказывать по индукции. Пусть вершина э получила свою постоянную метку на Й-й итерации, т. е.
после й-го выполнения п. 3. При й= 1 справедливость утверждения очевидна. Предположим, что оно верно для вершин, получивших свои постоянные метки на итерациях 2, 3, ..., й — 1. Обозначим через Р' (г, и)- путь, построенный алгоритмом в результате Й итераций, а через Р* — кратчайший (г, и)-путь. По условию ю(Р )= 1(и). Пусть У~ и Гэ — множества вершин, имеющих соответственно постоянные и временные метки перед началом й-й итерации.
Рассмотрим две возмоягные ситуации: а) Путь Р* содерясит вершины из Гэ. Пусть э — первая (считая от г) такая вершина, принадлежащая Р*, а вершина э' предшествует Р яа пути Р*, т. е. (э, Р)~н ~ АР*. Согласно выбору э имеем э' ш Кь Обозначим через Р, часть пути Р* от з до б. По предположению индукции 1(и') — вес кратчайшего (г, и') -пути. Поэтому ш(Р~) = 1(э') + ю(ио) >1(н). (1) Поскольку 1(э) — временная метка, а постоянная метка 1(и) вершины и выбирается па й-й итерации как наи- меньшая нз временных, то 1(р)»1(э). Объединив это неравенство с (1), получим ю(Рэ) ) и (Р ) ) 1(э) = ш(Рэ), т, е, 1'э — кратчайший (г, и)-путь.
б) Все вершины пути Р" входят в Гь Пусть э' и э" — такие вершины, что (и', э)~в АР" и (и", э)ш АРэ. Обозначив через Р' часть пути Р* от з до и', согласно предположению индукции имеем ю(Р')»1(и ). Поэтому, если э = г", то сразу получаем неравенство ю(Р )= ю(Р')+ и(и' э)»1(э')+ ю(н' э)= ш(Р ). Допустим теперь, что э Ф и . Поскольку и получает по- стоннную метку Пн) из э, а пе из и, то э(рэ) 1(э )+ ц,(э э)»1(э-)+ ц,(э э) щ(Рэ) Таким образом, и в случае б) верно неравенство и>(Р')( ~ ю(Р*), т. е. Рэ — кратчайший (г, и)-путь. Оцепим теперь трудоемкость алгоритма.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
