III Международная студенческая научная конференция Студенческий научный форум - 2011

Анализ алгоритмов, применяемых в настоящее время для поиска кратчайших путей между вершинами графа,  позволил выявить алгоритмы Уоршолла, Дейкстры, Форда [1]. Все алгоритмы характеризуются разными вычислительными затратами и позволяют решать поставленную задачу, но наиболее эффективным считается алгоритм Дейкстры,  предложенный в 1959 году.

Перед началом  выполнения алгоритма все вершины и дуги не отмечены. Каждой вершине в ходе выполнения алгоритма присваивается число d(x_i), равное длине кратчайшего пути из   x_i  в  x_j, включающего только отмеченные вершины.

Выполняется присвоение начальных значений, для чего необходимо обозначить d(x_i) пометку  исходной вершины и  считать, что  d(x_i) = 0. Отметить постоянной пометкой исходную вершину x_i  и  положить  y = x_i,  где y - последняя из отмеченных вершин. Остальные вершины имеют временные пометки и считать, что для x_j ≠ y   d(x_j) = ∞. Алгоритм   итерационный. Каждая итерация состоит из ряда шагов. Алгоритм  Дейкстры  рассмотрен  на примере  взвешенного графа  (рисунок 1, a).    Матрица  весов  дуг приведена на рисунке 1,b. Требуется найти кратчайший путь от  вершины   x₁   до   вершины   x_{6 .}

Выполняется присвоение начальных значений:    d(x₁) = 0;    x_i ≠ x₁   d(x_i) = ∞.

Для  каждой  итерации, в соответствующую строку таблицы 1 заносится отмеченная вершина и  текущие значения d(x_i). Для 1-й итерации будем иметь:

y  = x₁.    Г(x₁) = {x₂, x₃, x₄}.  Для всех вершин, входящих в Г(x₁), пометки которых временные, необходимо пересчитать d(x_i) в виде:

d(x₂) = min [d(x₂), d(x₁) + t(x₁, x₂)] = min [∞, 0 + 4] = 4. Аналогично для d(x₃) , d(x₄). Массив временных пометок будет иметь вид:  {d(x₂), d(x₃) , d(x₄)} = {4, 3, 7}.

Поскольку величина  d(x₃) = 3  является минимальной, то вершина  x₃  отмечается  x₃*.  Также отмечается и дуга (x₁, x₃)*.  Наименьшее из значений  d(x_i)  среди неотмеченных вершин в  таблице 1 выделено полужирным шрифтом.

Текущее дерево кратчайших путей состоит из дуги (x₁, x₃)*  (рисунок 2,а).

Таким образом, выполнив еще 4 итерации, получим окончательно построенное  дерево кратчайших путей, которое состоит из дуг   (x₁, x₃)*, (x₁, x₂)*,  (x₃, x₅)*,  (x₂, x₄)*  и (x₅, x₆)* (рисунок 2,д).

Кратчайший  путь, соединяющий   вершину   x₁   с   вершиной   x₆,  состоит из дуг  (x₁, x₂), (x₂, x₅)  и  (x₅, x₆) имеет длину  4+2+2 =8. Это не единственный кратчайший путь между вершинами  x₁  и  x₆. Путь, состоящий из дуг  (x₁, x₃), (x₃, x₅)  и  (x₅, x₆) имеет длину  3+3+2 =8 и также является кратчайшим путем между вершинами  x₁  и  x₆.

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

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

Литература

1. Майника Э. Алгоритмы оптимизации на сетях и графах. - М.: Мир, 1981. - 324 стр.

2. Новиков Ф. А. Дискретная математика для программистов. - Спб: Питер, 2000. - 304стр.

3. Хаггарти Р. Дискретная математика для программистов. - М.: Техносфера, 2005. - 400стр.