Построение математической модели и методы ее реализации

Нахождение кратчайших путей в графе

Начальные понятия

Будем рассматривать ориентированные графы G = <V, E> дугам которых приписаны веса. Это означает, что каждой дуге? E поставлено в соответствие некоторое вещественное число a (u, v), называемое весом данной дуги.

Нас будет интересовать нахождение кратчайшего пути между фиксированными вершинами s, t? V. Длину такого кратчайшего пути мы будем обозначать d (s, t) и называть расстоянием от s до t (расстояние, определенное таким образом, может быть отрицательным). Если не существует ни одного пути из s в t, то полагаем d (s, t) = +. Если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем, т.е. в последовательности v1,…, vp не будет повторов.

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

Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам, а каждая дуга - некоторому пути, длина которого представлена весом дуги. Мы ищем затем кратчайшие пути между городами. Вес дуги также может соответствовать стоимости (или времени) передачи информации между вершинами. В таком случае мы ищем самый дешевый (или самый скорый) путь передачи информации. Еще одну ситуацию получаем, когда вес дуги равен вероятности p (u, v) безаварийной работы канала передачи информации. Если предположить, что аварии каналов не зависят друг от друга, то вероятность исправности пути передачи информации равна произведению вероятностей составляющих его дуг. Задачу нахождения наиболее надежного пути легко можно свести к задаче о кратчайшем пути, заменяя веса p (u, v) на a (u, v) = - lg p (u, v).

Сначала рассмотрим алгоритмы нахождения расстояния между вершинами, а не самих путей. Однако, зная расстояние, мы можем при условии положительной длины всех контуров легко определить кратчайшие пути. Для этого достаточно отметить, что для произвольных s, t,? V (s, t) существует вершина v, такая что d (s, t) = d (s, v) + a (v, t).

Действительно, таким свойством обладает предпоследняя вершина произвольного кратчайшего пути из s в t. Далее мы можем найти вершину u, для которой d (s, v) = d (s, u) + a (u, v), и т.д.

Из положительности длины всех контуров легко следует, что созданная таким образом последовательность t, v, u,… не содержит повторений и оканчивается вершиной s. Очевидно, что она определяет (при обращении очередности) кратчайший путь из s в t.

Далее мы можем найти вершину u, для которой d (s, v) = d (s, u) + a (u, v), и т.д.

Из положительности длины всех контуров легко следует, что созданная таким образом последовательность t, v, u,… не содержит повторений и оканчивается вершиной s.

Очевидно, что она определяет (при обращении очередности) кратчайший путь из s в t.

Таким образом, мы получаем следующий алгоритм:

Алгоритм нахождения кратчайшего пути

Данные: Расстояния D[v] от фиксированной вершины s до всех остальных вершин v? V, фиксированная вершина t, матрица весов ребер, A [u, v], u, v? v.

Результаты: СТЕК содержит последовательность вершин, определяющую кратчайший путь из s в t.

begin:=?; CTEK? t; v:= t;v? s do:= вершина, для которой D[v] = D[u] + A [u, v];? u;:= u.

Пусть - ориентированный граф, | V| = n, | E| = m. Если выбор вершины u происходит в результате просмотра всех вершин, то сложность нашего алгоритма - O(n2). Если мы просматриваем только список ПРЕДШ[v], содержащий все вершины u, такие что u (r) v, то в этом случае сложность будет O(m).

Отметим, что в случае положительных весов ребер задача о кратчайшем пути в неориентированном графе легко сводится к аналогичной задаче для некоторого ориентированного графа. С этой целью достаточно заменить каждое ребро {u, v} двумя дугами? u, v? и? v, u?, каждая с таким же весом, что и {u, v}.

Однако в случае неположительных весов это приводит к возникновению контуров с неположительной длиной.

Далее будем всегда предполагать, что G = < V, E> является ориентированным графом, |V| = n, |E| = m. В целях упрощения изложения и избежания вырожденных случаев при оценке сложности алгоритмов будем исключать ситуации, при которых «большинство» вершин изолированные.

Будем также предполагать, что веса дуг запоминаются в массиве A [u], u, v? V (A [u, v] содержит вес a (u, v)).

Кратчайшие пути от фиксированной вершины

Большинство известных алгоритмов нахождения расстояния между двумя фиксированными вершинами s и t опирается на действия, которые в общих чертах можно представить следующим образом: при данной матрице весов дуг A [u, v], u, v? V, вычисляются некоторые верхние ограничения D[v] на расстояния от s до всех вершин v ОV. Каждый раз, когда мы устанавливаем, что D[u] + A [u, v] < D[v], оценку D[v] улучшаем: D[v] = D[u] + A [u, v].

Процесс прерывается, когда дальнейшее улучшение ни одного из ограничений невозможно. Легко можно показать, что значение каждой из переменных D[v] равно тогда d (s, v) - расстоянию от s до v. Заметим, что для того чтобы определить расстояние от s до t, мы вычисляем здесь расстояния от s до всех вершин графа. Не известен ни один алгоритм нахождения расстояния между двумя фиксированными вершинами, который был бы существенным образом более эффективным, нежели известные алгоритмы определения расстояния от фиксированной вершины до всех остальных.

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

Сначала представим алгоритм для общего случая, в котором предполагается только отсутствие контуров с отрицательной длиной. С эти алгоритмом обычно связывают имена Л.Р. Форда и Р.Е. Беллмана.