Назад

Методы программирования

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

Общая информация

Задание состоит из двух частей, обе обязательны для выполнения.

Теория

В этом задании рассматриваются два алгоритма поиска кратчайшего пути во взвешенном графе: алгоритм Флойда и алгоритм Дейкстры.

Алгоритм Флойда (Floyd)

Алгоритм Флойда (также известный как алгоритм Флойда-Уоршэлла, Floyd-Warshall) предназначен для поиска кратчайших путей между всеми парами вершин взвешенного графа. Пусть граф задан матрицей смежности A[N][N] по следующему правилу: A[i][j] равно

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

for (i = 0; i < N; i++) /* будем улучшать путь через i-ю вершину */
    /* перебираем все пары вершин */
    for (j = 0; j < N; j++)
        for (k = 0; k < N; k++)
            if (A[j][k] > A[j][i] + A[i][k])
             /* если пойти из j в i, а из i в k выгоднее, чем пойти напрямую из j в k */
                 A[j][k] = A[j][i] + A[i][k];
                 /* улучшаем путь из j в k */

Иллюстрация к алгоритму Флойда

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

Для определения кратчайших путей (т.е. вершин, через которые проходит кратчайший путь) приходится воспользоваться дополнительным массивом C[N][N]. Существует несколько способов заполнения массива C и определения кратчайшего пути:

  1. Изначально C[i][j] = i, при изменении значения
        A[j][k] = A[j][i] + A[i][k]
    производится также изменение значения C[j][k]:
        C[j][k] = C[i][k].
    В этом случае значение массива C[j][k] после окончания алгоритма будет указывать вершину, предпоследнюю в пути от j к k, и восстановление пути будет возможно сделать простым циклом;

  2. Изначально C[i][j] = -1, при изменении значения
        A[j][k] = A[j][i] + A[i][k]
    производится также изменение значения C[j][k]:
        C[j][k] = i.
    В этом случае значение массива C[j][k] после окончания алгоритма будет указывать одну из вершин, через которую проходит путь от j к k, и восстановление пути будет возможно сделать простым циклом либо при помощи рекурсивной функции.

Алгоритм Флойда требует O(N3) времени для работы и O(N2) памяти для хранения матрицы C. Для корректной работы алгоритма необходимо, чтобы в графе отсутствовали циклы отрицательной длины (в этом случае понятие кратчайшего пути не определено).

Алгоритм Дейкстры (Dijkstra)

Алгоритм Дейкстры предназначен для нахождения кратчайших путей от одной вершины взвешенного графа до всех остальных вершин. Пусть граф представлен в виде матрицы смежности A[N][N] (определенной как в алгоритме Флойда) и необходимо найти кратчайшие пути из вершины с номером start. Алгоритм использует тот факт, что любая часть кратчайшего пути сама является кратчайшим путем между соотвествующими вершинами.

Создадим массив длин путей d[N], в каждом элементе которого будем хранить длину кратчайшего (из известных на текущий момент) пути от start до соответствующей вершины. Изначально d[start] = 0 и d[i] равно бесконечности для всех i != start. Создадим также массив used[N] и заполним его нулями. Алгоритм может быть сформулирован следующим образом:

  1. Из всех неиспользованных вершин (все i такие, что used[i] == 0) выберем вершину с минимальным d[i], не равным бесконечности. Обозначим эту вершину как curr. Если выбрать такую вершину невозможно, завершим выполнение алгоритма.
  2. Пометим вершину curr как использованную, присвоив used[curr] = 1.
  3. Для каждой неиспользованной вершины i сравним значение d[i] с суммой d[curr] + A[curr][i]. Если d[i] > d[curr] + A[curr][i], то присвоим d[i] = d[curr] + A[curr][i].
  4. Перейдем к шагу 1.

После выполнения алгоритма массив d будет содержать длины кратчайших путей от вершины start до всех остальных вершин. В случае, если до какой-либо вершины невозможно добраться из вершины start, соответствущий элемент массива d будет равен бесконечности.

Для определения кратчайших путей необходимо ввести еще один одномерный массив c[N]. Пусть первоначально он заполнен числами -1. В шаге 3 алгоритма Дейкстры, делая присваивание
    d[i] = d[curr] + A[curr][i],
будем изменять значение c[i]:
    с[i] = curr.
После окончания алгоритма значение c[i] будет указывать вершину, предпоследнюю в кратчайшем пути от start до i, и сам путь восстанавливается простым циклом.

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

Формулировка задания

a. Алгоритм Флойда

Прочитать из файла input.txt граф, заданный там списком ребер с весами. Подсчитать длины кратчайших путей из каждой вершины в каждую, вывести кратчайший путь между какой-либо парой вершин.

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

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