Алгоритмы поиска кратчайших путей Дейкстры и Флойда

Обычно в практических задачах длина пути измеряется не числом дуг, а их суммарной длиной. Термин длина носит обобщенный смысл. Синонимами этого термина являются расстояние, вес, стоимость дуг, причем могут рассматриваться и отрицательные значения.

Рассмотрим два алгоритма поиска кратчайших путей между вершинами: Дейкстры и Флойда. Будем считать, что длина дуги из вершины V_i в вершину V_j задана элементом матрицы a_ij, причем a_ii=0 и a_ij =¥, если дуга из вершины V_i в вершину V_j отсутствует.

В алгоритме Дейкстры находится кратчайший путь из вершины S в вершину T. Вершинам присваиваются временные и окончательные метки, которые будем обозначать соответственно буквами C и D с индексами вершин.

1. Вершине S присваивается окончательная метка 0, то есть C_s:=0, временным меткам остальных вершин – значение ¥.

2. Пусть i – номер последней вершины, которой присвоена окончательная метка C_i. Каждой вершине j, имеющей временную метку D_j, присваивается новая временная метка по правилу D_j:=min(C_i+a_ij , D_j). Если значение D_j меняется, то вместе с ним сохраняется номер предыдущей вершины i.

3. Наименьшая из временных меток объявляется окончательной. Пусть k – номер этой вершины. Следовательно, C_k:=D_k. Если вершина T не получила окончательной метки, то i:=k и переход к 2.

4. Конец.

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

Пусть имеется следующий граф.

3

2

Требуется найти кратчайший путь из вершины A в вершину C.

Этапы расстановки меток удобно представить в виде таблицы. Окончательную метку будем отмечать жирным шрифтом и подчеркиванием. В скобках указывается предыдущая вершина.

Итак, длина кратчайшего пути равна 3. Окончательная метка 3 для вершины C получена из предыдущей вершины D. В свою очередь окончательная метка 2 для вершины D получена из вершины A. Следовательно, кратчайший путь составляют вершины A, D, C.

Значения окончательных меток появляются по возрастанию, то есть алгоритм Дейкстры обеспечивает поиск в ширину. Алгоритм не работоспособен при наличии отрицательных расстояний, что иллюстрирует следующий простой пример

-3

1

Здесь кратчайший путь из A в C проходит через вершину B и равен -1, тогда как по алгоритму Дейкстры вершина C сразу получит окончательную метку 1.

Трудоемкость алгоритма Дейкстры пропорциональна величине N ², где N – количество вершин графа.

Алгоритм Флойда определяет кратчайшие пути между всеми парами вершин. Снова будем считать, что длина дуги из вершины V_i в вершину V_j задана элементом матрицы a_ij, причем a_ii=0 и a_ij =¥, если дуга из вершины V_i в вершину V_j отсутствует.

Пусть элемент a_ij^(k) матрицы A^(k) равен длине кратчайшего пути из вершины V_i в вершину V_j, с номерами промежуточных вершин, не превосходящими k. Тогда выполняется рекуррентное соотношение

(*)

Действительно, кратчайший путь из V_i в V_j с номерами промежуточных вершин, не превосходящими k+1, может не проходить через вершину V_k+1 . В противном случае он представляет собой кратчайший путь из V_i в V_k+1, а затем из V_k+1 в V_j.

В качестве A⁽⁰⁾ выбирается исходная матрица A. Матрица A⁽ⁿ⁾ даст длины кратчайших путей между всеми парами вершин без каких-либо ограничений на промежуточные вершины. Значение a_ij⁽ⁿ⁾ = ¥ означает отсутствие пути из вершины V_i в вершину V_j.

Параллельно с описанными матрицами строится последовательность матриц B⁽ⁱ⁾ для нахождения самих кратчайших путей. Элемент b_ij^(k) матрицы B^(k) устанавливается равным номеру второй вершины на кратчайшем пути из V_i в V_j с номерами промежуточных вершин, не превосходящими k, и 0 в случае отсутствия путей. Элемент b_ij^(k+1) не меняется, если в формуле (*) минимум достигается на первом значении, и полагается равным b_ik+1^(k), если минимально второе выражение, так как в этом случае кратчайший путь проходит через вершину V_k+1.

Первоначально b_ij⁽⁰⁾ матрицы B⁽⁰⁾ полагается равным j, если есть дуга из V_i в V_j, и 0, если такая дуга отсутствует. Матрица B⁽ⁿ⁾ позволяет восстановить кратчайший путь между любыми двумя вершинами. Действительно, если s=b_ij⁽ⁿ⁾ дает вторую вершину на кратчайшем пути из V_i в V_j, то t=b_sj⁽ⁿ⁾ даст третью вершину, w=b_tj⁽ⁿ⁾ - четвертую и так далее до попадания в вершину V_j. Значение b_ij⁽ⁿ⁾ =0 означает отсутствие пути из вершины V_i в вершину V_j.

Рассмотрим в качестве примера следующий граф, в котором вершины идентифицированы номерами

3

1

Для него матрицы A⁽⁰⁾ и B⁽⁰⁾ имеют соответственно вид

На первом шаге допускаются пути, проходящие через вершину 1. Поскольку появляется путь 4-2-1, изменения затронут вторые элементы четвертой строки, то есть матрицы A⁽¹⁾ и B⁽¹⁾ примут вид

На втором шаге допускаются пути, проходящие через вершины 1 и 2. Добавляются пути 1-2-3 и 4-1-2-3. Последний путь имеет большую длину, чем имеющаяся дуга 4-3, поэтому матрицы A⁽²⁾ и B⁽²⁾ примут вид

и так далее. Кратчайшие пути между всеми парами вершин будут представлены следующими матрицами A⁽⁴⁾ и B⁽⁴⁾