Алгоритмы на графах. Поиск кратчайших путей

Лекция 8: Алгоритмы на графах. Поиск кратчайших путей.

0  Введение

Многие задачи связаны с поиском кратчайших путей на графе. В этой лекции мы рассмотрим некоторые из них.

1  Алгоритм Дейкстры

Алгоритм Дейкстры решает задачу о кратчайших путях для взвешенного ориентированного графа, в котором веса всех ребер неотрицательны (w(u,v) – вес ребра между вершинами u и v). Алгоритм находит кратчайшие пути из заданной вершины s во все остальные.

Алгоритм использует массив m[n] (i-й элемент хранит кратчайшее расстояние от начальной вершины до i-й). Вершина может иметь пометку и предшественника p.

1.  Инициализация. Массив m инициализируется значением ∞. Со всех вершин сняты пометки. Ни у какой вершины не указан предшественник. m[s] = 0 (расстояние от начальной вершины до вершины s равно 0).

2.  Общий шаг. Среди всех непомеченных вершин найти такую вершину u, для которой m[u] минимально. Для всех вершин v, связанных ребром с u, проверить условие m[u]+w(u,v)≤m[v] (расстояние до вершины v через u меньше, чем вычисленное раньше). Если это так, то m[v]=m[u]+w(u,v), p[v]=u. Пометить вершину u.

3.  Шаг 2 повторять до тех пор, пока есть непомеченные вершины.

После выполнения алгоритма массив m будет хранить кратчайшие расстояния от начальной вершины. Кратчайший путь можно восстановить, используя предшественника p.

Доказательство алгоритма Дейкстры можно найти в литературе.

2  Алгоритм Беллмана-Форда

Алгоритм Беллмана-Форда решает задачу о кратчайших путях для взвешенного ориентированного графа, ребра которого могут иметь отрицательный вес. Если в графе существует цикл отрицательного веса, алгоритм вернет значение ложь.

1.  Инициализация. Такая же, как и в алгоритме Дейкстры.

2.  Итерация. |V| раз выполнить шаг 3.

3.  Общий шаг. Для каждого ребра (u,v) выполнить: проверить условие m[u]+w(u,v)≤m[v] (расстояние до вершины v через u меньше, чем вычисленное раньше). Если это так, то m[v]=m[u]+w(u,v), p[v]=u.

4.  Завершение. Если существует ребро (u,v), для которого m[v]>m[u]+w(u,v), вернуть ложь. Иначе вернуть истину.

3  Алгоритм Флойда-Уоршелла

Алгоритм Флойда-Уоршелла выполняет поиск кратчайших путей для всех пар вершин. Алгоритм допускает ребра отрицательного веса, но не допускает циклы отрицательного веса.

for k = 1 to |V| do

        for i = 1 to |V| do

                 for j = 1 to |V| do

                          w[i, j] = min(w[i, j], w[i, k] + w[k, j])

Перед выполнением алгоритма длина дуги (i,j) равна w[i, j], после выполнения w[i, j] содержит кратчайшее расстояние от вершины i до вершины j.

4  Задания

1.  Оцените время работы приведенных алгоритмов.

2.  Докажите корректность алгоритма Флойда-Уоршелла.

5  Задачи

1.  Сыр

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

В сыре живет мошка. Она может передвигаться в сыре путем рытья нор со скоростью один миллиметр за секунду. Время передвижения мошки в полости равно нулю.

Мошка должна перебраться из одной полости в другую за кратчайшее время.

Полости задаются трехмерными координатами центра и радиусом.

2.  Арбитражные операции

Арбитражными операциями называется следующий способ извлекать прибыль из несогласованности курсов обмена валют. Предположим, что один доллар можно обменять на 0.7 фунта стерлингов, один фунт стерлингов – на 9.5 франков, один франк – на 0.16 доллара. Тогда, обменивая 1 доллар в указанной последовательности, в результате можно получить 1.064 доллара и тем самым остаться с прибылью 6.4%.

Пусть имеются n валют и массив R[1..n, 1..n], в котором записаны курсы обмена (единицу валюты i можно обменять на R[i, j] единиц валюты j).

Разработайте алгоритм, печатающий такую последовательность (i₁,i₂…i_k), что

R[i₁,i₂]…R[i_k-1,i_k]R[i_k,i₁] > 1.

Оцените время его работы.

3.  Лабиринт

В лабиринте, который имеет форму прямоугольника M×N (1≤M,N≤100), стены изображаются с помощью цифры 1, а свободное пространство коридора — 0. Выход из лабиринта находится в точке с координатами (1,1) (левый верхний угол). Робот, который размещен в одной из клеток лабиринта (цифра 2), может двигаться только вдоль коридора, перемещаясь за один шаг только на соседнюю клетку вверх, вниз, влево или вправо. Выходить за границы массива запрещено.

Напишите программу для определения длины самого короткого пути выхода робота из лабиринта.

6  Список литературы

Т. Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы. Построение и анализ, М., МЦНМО.

В.М. Бондарев, В.И. Рублинецкий, Е.Г. Качко. Основы программирования. Издательство Фолио. Харьков, 1997.