Олимпиады по программированию

olympiads.ru

МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Занятие 5. Графы: поиск кратчайшего пути, обход в ширину.

Путь в графе между парой вершин V и U - это последовательность вершин L_i (0 <= i <= k), удовлетворяющих условиям:
 1) L₀=V
 2) L_k=U
 3) для любого i (0 <= i <= k-1) вершины L_i и L_i+1 соединены ребром.

Пусть дан невзвешенный граф с N вершинами и M ребрами. Требуется найти кратчайший путь между двумя вершинами. Под кратчайшим расстоянием в невзвешенном графе понимается минимально возможное число ребер в пути между парой вершин.

Будем решать чуть более общую задачу: искать кратчайшее расстояние от начальной вершины до всех остальных. Рассмотрим два способа ее решения.

Волновой алгоритм
Заведем массив, в котором для каждой вершины будем хранить длину кратчайшего пути от начальной вершины до нее. Если путь еще не известен, запишем в соответсвующий элемент массива бесконечность (под бесконечностью будем подразумевать некоторое очень большое число, которое заведомо больше ответа, который мы можем получить, например, в качестве бесконечности можно использовать максимальное значение, которое могут принимать переменные того типа, в котором мы ведем вычисления, либо число, которое мы заведомо не можем получить в качестве ответа, например, число -1 (длина пути не может быть отрицательна) ).

В начале работы алгоритма нам известна только длина пути до начальной вершины, она равна 0. Рассмотрим все вершины, соседние с начальной, расстояние до каждой из них равно 1. Рассмотрим все вершины, являющиеся соседями для вершин, расстояния от начальной вершины до которых равно 1. Если расстояние до такой вершины еще не посчитано, то оно равно 2, и так далее. Таким образом, на k-ом шаге мы находим все вершины, расстояние до которых равно k-1: найдя такую вершину, перебираем все соседние с ней вершины, и, если расстояние до нее еще не посчитано, то оно равно k. Если на некотором шаге мы не изменили ни одного числа в массиве - длины всех путей найдены. Заметим, что кратчайший путь до вершины не может иметь длину больше, чем N-1.

Поиск в ширину
Заметим недостаток предыдущего алгоритма: чтобы на k-том шаге найти вершины, расстояние до которых равно k-1, нужно просмотреть все вершины. Попытаемся исправить этот недостаток.

Заведем очередь. Вероятно, что в жизни очередь видели все. По мере поступления, объекты помещаются в очередь. Когда "продавец" очереди освобождается, он извлекает из очереди следующий элемент и "обслуживает" его. Очередь часто удобно реализовывать с помощью массива и двух указателей - на первый "необслуженный" элемент, и первый свободный элемент массива. Тогда добавление элемента в очередь выглядит так: помещаем его в элемент массива, на который указывает 2-й указатель, с увеличиваем этот указатель на 1. Извлечение из очереди столь же просто: берем элемент, на который указывает 1-й указатель, и указатель увеличиваем на 1.

Вернемся к поиску длин кратчайших путей. Изначально поместим в очередь один элемент - начальную вершину. До нее расстояние известно и равно 0. На каждом шаге алгоритма извлекаем из очереди одну вершину (пусть это вершина v и до нее расстояние k). Затем пербираем всех соседей данной вершины, расстояние до которых еще не известно и добавляем их в очередь. Расстояние до них записываем k+1. Алгоритм заканчивается, когда очередь опустеет. Этот алгоритм работает быстрее предыдущего. Время работы алгоритма зависит от конкретной реализации. Обычно алгоритм выполняет порядка N² или M действий.

Восстановление пути
Пусть мы знаем кратчайшие расстояния до всех вершин. Как найти кратчайший путь до конкретной вершины? Рассмотрим эту вершину (обозначим ее V). Пусть длина пути до нее L. Эта вершина является последней в пути к V. Найдем какую-нибудь вершину, которая соединена с V, и расстояние до которой равно L-1. Тогда эта вершина является предпоследней в пути (если таких вершин несколько, значит существует несколько кратчайших путей и можно выбрать любую из этих вершин). Далее найдем вершину, которая соединена с предпоследней и расстояние до которой равно L-2. Она является пред-предпоследней. Продолжая этот процесс мы можем "раскрутить" весь путь задом наперед. Осталось только запомнить его в массиве и вывести в правильном порядке.