Поиск кратчайшего пути во взвешенном графе

Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается. Нахождение кратчайшего пути жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (напр. кратчайший путь от дома до академии), также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet и мн. др.

В общем виде задачу можно сформулировать так:

Дан простой взвешенный граф G (V, E) без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.

На бытовом уровне можно переформулировать ее таким образом:

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

Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.

В данном пособии будут рассматриваться алгоритмы Дейкстры и Флойда-Уоршелла. Это основные алгоритмы для решения данной задачи. Существуют ещё методы, но мы их опустим, так как они либо имеют более плохую асимптотику, либо более трудны в реализации при одинаковой скорости работы. Вообще говоря, для решения олимпиадных задач это базовые алгоритмы, к которым, как правило, можно свести проблему.

Итак, нам необходимо найти кратчайший путь, то есть путь с минимальным весом, между двумя вершинами графа. Эта задача разбивается на 2 подзадачи: нахождение величины пути и вывода самого пути. Пусть нам уже дана матрица кратчайших путей D[1.n], где D[i] храниться кратчайшее расстояние от стартовой вершины (пусть для определенности это вершина 1) до вершины с номером i, причем D[1] = 0. Для двух вершин a и b существует такая вершина c (без ограничения общности скажем, что с смежна с b), что D[b] = D[c] + mass[c][u], где mass — матрица смежности. То есть, при прохождении по кратчайшему пути мы из c попадем в b. Иначе говоря, с является «предком» b. Если создать массив «предков», в котором для каждой вершины будет храниться ее предок, то мы без труда выведем путь от стартовой вершины до любой другой.

Вот рекурсивный пример такого вывода на С++ (par — массив предков):

void Out (int v).

{.

if (v == s).

{.

cout << v + 1 << ««;

}.

else.

{.

Out (par[v]);

cout << v + 1 << ««;

}.

}.

Для вывода пути необходимо запустить процедуру с номером последней вершины (финиша).

Теперь самое время научиться решать первую задачу — находить эти кратчайшие пути. Рассмотрим два алгоритма: Дейкстры и Флойда-Уоршелла.

Приложение. Время работы программы К большинству олимпиадных задач ограничения (по времени, по памяти) жюри подбирает по принципу «как можно больше». То есть чтобы любые разумные реализации правильного решения проходили, а всё остальное — нет. Когда встречается задача с маленькими ограничениями (например, до 10), это означает, что-либо автор намеренно сбивает Вас с правильного пути, либо действительно эта задача решается каким-то (оптимизированным) перебором. Ну, а если ограничения на основную входную величину, определяющую (как правило) будущий алгоритм, составляет порядка 109, то пройдет только однопроходной алгоритм.

Среднестатистический компьютер (в реальности) выполняет примерно 1 — 3 миллиона операций в секунду. Исходя из этого, надо выбирать метод решения той или иной задачи, предварительно прочитав ограничения на входные данные. Следует сразу соображать, какой алгоритм следует использовать (или определиться, какой не использовать точно).

Пусть n — входное число, определяющее скорость будущего решения. Тогда скорость работы алгоритма может быть пропорциональна какой-либо функции от n. Например, корень из, log2n, n2, 2n и т. д. Итак, определимся сразу, какой алгоритм будем выбирать исходя из входных данных так, чтобы количество операций проходило по временным ограничениям (как правило, на олимпиадах это 2 секунды):

• 1) для n > 1 000 000 000 проходит решение за n операций впритык;
• 2) 1 000 000 < n < 10 000 000 обычно log2n, хотя бывает и (log2n) 2;
• 3) для 100 000 < n < 500 000 обычно n*log2n;
• 4) n < 5000 — это n2;
• 5) порядка 100−200 n3;
• 6) менее 20−24 — это 2n.

Временную сложность процесса будем обозначать O (f), f — некоторая функция от n (например, одна из вышеописанных).

Для (1) характерны так называемые однопроходные алгоритмы, которые обрабатывают информацию и решают задачу одновременно при считывании данных, а также линейные алгоритмы обходов графа в ширину и глубину; для (2) можно привести пример алгоритма бинарного поиска элемента в отсортированном массиве; для (3) — сортировка массива «кучей» (heap sort); (4) — с такой асимптотикой работают очень многие алгоритмы, например, алгоритм Дейсктры; для (5) — алгоритм Флойда; для (6) — переборные алгоритмы (комбинаторика).