*5.18. Покажите, что алгоритм нахождения кратчайшего пути из разд. 5.8 работает, когда некоторые ребра имеют отрицательную стоимость, но никакой цикл не имеет отрицательной стоимости. Что случится, если у какого-нибудь цикла будет отрицательная стоимость?

**5.19. Покажите, что положительные и отрицательные вещественные числа с +00 и -оо не образуют замкнутого полукольца. Как в этом свете объяснить упр. 5.18? Указание: Какие свойства замкнутого полукольца фактически используются в алгоритме 5.5?

5.20. Примените алгоритм 5.6 для нахождения кратчайшего расстояния от узла и, в каждый узел v графа G на рис. 5.37.

*5.21. Покажите, что задачу о нахождении кратчайшего пути из одного источника в случае неотрицательных стоимостей ребер для графа с е ребрами и п узлами можно решить за время О (е log п). Указание: Используйте подходящую структуру данных, чтобы строки 5 и 8 алгоритма 5.6 можно было эффективно вьшолнить при

**5.22. Покажите, что задачу о нахождении кратчайшего пути из одного источника в случае неотрицательных стоимостей ребер для графа с е ребрами и п узлами можно решить за время 0{ke+ -fftn + для любой фиксированной постоянной k.

begin

for veV-{v,} do D[v]l{v„, v); while 8ФУ do begin

выбрать такой узел wV-S, что D[w] принимает наименьшее значение; SSuH;

for vV, для которого D[v]>D[w]+l{w, v) do begin

D[v]D[w] + l(w, v); end

Рис. 5.38. Алгоритм нахождения кратчайшего пути из одного источника.

Рис. 5.39. Стоимости ребер для графа с 5 узлами.

*5.23. Докажите, что алгоритм нахождения кратчайшего пути, приведенный на рис. 5.38, строит кратчайший путь из Уо в каждый узел V произвольного графа, у которого могут быть ребра с отрицательными стоимостями, но циклов с отрицательными стоимостями нет.

*5.24. Каков порядок времени работы алгоритма, приведенного на рис. 5.38? Указание: Рассмотрите работу алгоритма на графе с 5 узлами, стоимости ребер которого указаны на рис. 5.39.

5.25. Постройте алгоритм, который распознавал бы, есть ли в данном ориентированном графе, ребрам которого приписаны положительные и отрицательные стоимости, цикл отрицательной стоимости.

5.26. Измените правило выбора узла w в алгоритме на рис. 5.38 так, чтобы гарантировать оценку времени 0(/г) в случае, когда ребрам приписаны произвольные стоимости.

5.27. Напишите алгоритм, который по данной (пХп)-матрице М положительных целых чисел строил бы последовательность смежных элементов, начинакщуюся с Л1[/г, 11 и оканчивающуюся М[1, п], так, чтобы минимизировать сумму абсолютных значений разностей между соседними элементами. Два элемента M.U, /] и M{k, I] считаются смежными, если (а) i-k±l и /=/ или (б) ik и /=/±1. Например, для рис. 5.40 решением будет последовательность 7, 5, 8, 7, 9, 6, 12.

5.28. Алгоритм на рис. 5.24 для каждого о € V вычисляет наименьшую стоимость пути среди всех путей из Уо в у. Модифицируйте этот алгоритм так, чтобы он строил некоторый путь наименьшей стоимости для каждого узла у из V.

19 6 12

8 7 3 5

5 9 11 4

L7 3 2 6J

Рис. 5.40. Матрица положительных целых чисел.

**5.29. Напишите программу, реализующую доминаторный алгоритм из разд. 5.11.

Проблемы для исследования

5.30. Для многих проблем, связанных с графами, поиск в глубину мог бы принести пользу. Одна из них касается k-связности. Неориентированный граф называется k-связным, если для каждой пары узлов V к W существуют такие k путей между ними, что ни один узел (кроме у и tw) не входит более чем в один путь Таким образом, двусвязность означает 2-связность. Хопкрофт, Тарьян [197361 построили алгоритм, отыскивающий 3-связные компоненты за линейное время. Естественно выдвинуть гипотезу, что для каждого k есть алгоритм, отыскивающий /г-связные компоненты за линейное (по числу узлов и ребер) время. Не сможете ли вы найти такой алгоритм?

5.31. Другой интересной проблемой, для решения которой, быть может, нужен поиск в глубину (а, быть может, и нет), является построение алгоритма, отыскивающего за линейное (по числу ребер) время остовное дерево наименьшей стоимости.

5.32. Заслуживает рассмотрения и задача нахождения кратчайшего пути из одного источника, когда е<. Существует ли алгоритм, отыскивающий за время О (е) хотя бы кратчайшее расстояние между двумя конкретными точками? Читателю было бы полезно ознакомиться с упр. 5.21 и 5.22, основанными на диссертации Джонсона [1973], а также с работой Спиры, Пана [1973], в которой показано, что в общем случае для таких алгоритмов требуется rtV4 сравнений, если алгоритмы используют только сравнения между суммами стоимостей ребер. Вагнер [1974] применил технику сортировки вычерпыванием, чтобы получить алгоритм сложности 0(e) в случае, когда в качестве стоимостей ребер фигурируют малые целые числа.

5.33. Было показано (Керр [1972]), что если допускаются только операции MIN и -Ь, то проблема нахождения кратчайших путей между всеми парами узлов требует kn шагов, где k - некоторая положительная постоянная. Рабин усилил этот результат до rtV6. Тем не менее может оказаться, что если допустить другие операции, то можно будет получить алгоритм, работающий менее О (п) времени. Например, как мы увидим в следующей главе, можно построить транзитивное замыкание (или, что эквивалентно, перемножить две булевы матрицы) быстрее, чем за 0(п) шагов, если допустить операции, отличные от булевых.