В дальнейшем мы используем понятие сети, оно нуждается в некотором уточнении, так как нет единого подхода в его понимании. Под сетью подразумевается просто связный ориентированный граф D (V, Е), в котором, возможно, выделены вход и выход. Более узкое толкование термина «сеть» предполагает существование одного источника и одного стока, об этом по мере необходимости мы будем говорить отдельно. Нужно отметить, что существуют и другие толкования термина. Отметим также, что в ориентированном графе D (V, Е), как и в неориентированном G (V, Е), используется название «вершина», а не узел.

Описание алгоритма

Этот алгоритм используется для решения задачи о нахождении кратчайшего пути в сети без контуров. Пусть задана сеть из n + 1 вершин, то есть ориентированный граф. В нем выделены две вершины – вход (нулевая вершина) и выход (вершина с номером n). Для каждой дуги заданы числа, называемые длинами дуг. Длиной пути (контура) называется сумма длин входящих в него дуг (если длины дуг не заданы, то длина пути (контура) определяется как число входящих в него дуг).

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

Предположим, что в сети нет контуров. Тогда всегда можно пронумеровать вершины таким образом, что для любой дуги (i, j) имеет место j > i. Такая нумерация называется правильной. В сети без контуров всегда существует правильная нумерация.

Если изначально в задаче дается неправильная (произвольная) нумерация вершин, то, прежде чем использовать метод потенциалов, нужно определить правильную нумерацию, используя алгоритм топологической сортировки и алгоритм Уоршалла.

Рис. 15

Алгоритм Уоршалла заключается в вычислении транзитивного замыкания. Для того чтобы понять принцип алгоритма Уоршалла, рассмотрим пример. Пусть задан граф с произвольной нумерацией вершин (рис. 15). Составим для этого графа две матрицы смежности.

Номер строки в матрице соответствует номеру исходящей вершины, а номер столбца – входящей. Единица на пересечении i-й строки и j-го столбца ставится в том случае, если есть путь, выходящий из i-й вершины и входящий в j-ю. Во все остальные ячейки матрицы заносятся нули.

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

С помощью полученной матрицы смежности с транзитивным замыканием можно достроить на графе дополнительные дуги: добавленные в матрицу единицы обозначают новые дуги в графе (на рис. 12 они обозначены пунктиром).

Алгоритм топологической сортировки – это алгоритм дополнения частичного порядка на конечном множестве. За основу берется матрица смежности, полученная алгоритмом Уоршалла. Рассматриваем в ней столбцы. Выбираем столбец, содержащий только нулевые элементы, и условно его вычеркиваем вместе со строкой этого же номера. Номер этого столбца записываем, причем вариантов выкидывания может быть несколько из-за того, что может оказаться несколько таких столбцов. Остается матрица, меньшая предыдущей на столбец и строку, с ней проделывют ту же операцию, и так до тех пор, пока не останется один элемент, номер которого также записываем.

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

1 – 3 – 2 – 5 – 4

1 – 2 – 3 – 4 – 5

Это означает, что номеру, произвольно поставленному у вершины, соответствует другой номер, полученный в результате топологической сортировки. Чтобы теперь получить правильную нумерацию, необходимо заменить первоначальные номера вершин на правильные (на рисунках правильная нумерация дается в квадратных скобках).

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

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

Шаг 0: помечаем нулевую вершину (вход) индексом λ₀ = 0.

Шаг k: помечаем вершину k индексом λ_k = min ( λ_i + l_ik ).

Здесь используются следующие обозначения: l_ij – длина дуги (i, j); λ_n – потенциал вершины (индекс выхода), равный длине кратчайшего пути.

Кратчайший путь здесь ищется по принципу оптимальности Беллмана. Он формулируется так: если ищется кратчайший путь между двумя точками, то длина пути между любыми двумя точками кратчайшего пути также должна быть минимальна. Когда потенциалы установлены, кратчайший путь определяется методом обратного хода от выхода к входу, то есть кратчайшим является путь µ = (0; i₁; i₂; …; i_n-1; n), такой, что l_in;1n = λ_n – λ_n-1 и т.д.

Пример

На рис. 16 приведен пример применения метода потенциалов для определения кратчайшего пути.

Рис. 16

Задана сеть из 8 вершин, входом является вершина с номером 0, а выходом – вершина с номером 7. Числа у дуг равны длинам дуг. Нумерация вершин является правильной, т.к. для любой дуги (i, j) имеет место j > i.

Помечаем первую вершину (вход) индексом 0, т.е. потенциал этой вершины равен 0. Индексы вершин – потенциалы – на рисунке помещены в квадратные скобки.

Далее определяем потенциал для первой вершины. В первую вершину можно попасть только из нулевой, поэтому складываем потенциал этой вершины с длиной дуги между ними (то есть [0]+3=[3]). Потенциал первой вершины равен 3.

В отличие от первой во вторую вершину можно попасть либо из нулевой вершины, либо из первой. Определяем длины этих путей. В первом случае он будет равен 9 ([0]+9), а во втором – 8 (потенциал первой вершины + длина дуги между первой и второй вершиной, т.е. [3]+5). Из двух путей выбираем наименьший. Таким образом, потенциал второй вершины будет равен 8.

Определяя потенциал третьей вершины, рассматриваем пути только от ближайших вершин, то есть от первой и второй вершин. В первом случае путь равен 11, а во втором – 10. Соответственно потенциал 3-й вершины равен 10.

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

Задания

Определить кратчайший путь в графе.

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

Описание алгоритма

Предположим, что вершина 1 является вершиной-входом и требуется найти длины кратчайших путей от вершины 1 до каждой другой вершины графа. Для этого алгоритма дуговые расстояния могут быть как положительными, так и отрицательными, но не должно быть циклов отрицательной длины. Предположим, что если в графе отсутствует та или иная дуга, то её вес равен бесконечно большому числу. Основная идея алгоритма Беллмана – Форда состоит в том, чтобы сначала найти длины кратчайших путей, при условии, что пути содержат не более двух дуг, не более трех дуг и т.д. Кратчайший путь, при условии, что он содержит не более h дуг, будем называть кратчайшим путем в графе. Согласно идее Беллмана - Форда, Р. Прим предложил алгоритм нахождения длин кратчайших путей, ведущих из произвольной вершины графа во все остальные его вершины (в которые есть пути из вершины-входа), состоящий в присвоении вершинам некоторых потенциалов. Признаком окончания алгоритма является остановка процесса изменения потенциалов.