Поиск кратчайшего пути в графе

Пусть дан некоторый конечный граф G=(V,E), состоящий из N вершин, и две его вершины a, bÎV. Пусть для каждого ребра графа e задано положительное вещественное число l(e), которое будем называть длиной ребра. Требуется найти путь между вершинами графа a и b минимальной длины, т.е. требуется найти последовательность {x₁,…,x_n}, где x_iÎV, x₁=a, x_n=b, (x_i, x_i+1)ÎE с минимально возможной S l(x_i,x_i+1).

Стандартным решением данной задачи является алгоритм Дейкстры.

Основная идея алгоритма заключается в следующем.

Пусть множество Q_n представляет собой множество n ближайших вершин к вершине a вместе с длинами пути от a до этих вершин. Т.е. в каждом элементе множества q_iÎQ_n содержится номер соответствующей вершины x_i и длина пути от a до этой вершины l_i: q_i=(x_i,l_i). Можно предполагать, что последовательность {l_i} является неубывающей.

Утверждается, что ближайшая вершина графа к a из вершин, не внесенных в Q_n, задается следующим соотношением:

argmin(v,wÎV, wÎ Q_n, vÏ Q_n, (w, v) ÎE: l_w+|(w,v)|) (*)

здесь и далее под wÎ Q_n, vÏ Q_n имеется в виду, что w встречается среди вершин, внесенных в Q_n, а v – нет; длина ребра (w, v) обозначается |(w,v)|. Т.о. элемент q_n+1 складывается из вершины v, на которой достигается указанный минимум и соответствующей длины l_n+1 = l_w+|(w,v)|.

Доказательство. Допустим, найдена вершина sÏ Q_n с минимальной длиной до a. Пусть кратчайший путь от a до s проходит по последовательности вершин графа {a,x₂,…,x_n,s}. Длина пути {a,x₂,…,x_n} меньше длины пути до s, поэтому x_nÎ Q_n, но тогда длина пути {a,x₂,…,x_n,s} должна совпадать с длиной кратчайшего пути от a до найденного выше w.

¢

При поиске значения (*), формально, требуется перебрать все вершины wÎ Q_n и для каждой из них требуется перебрать все смежные вершины. Будем далее предполагать, что в графе отсутствуют кратные ребра и петли, тогда процедура (*) требует выполнения O(N²) операций, из чего следует, что суммарное время работы алгоритма есть O(N³).

На самом деле, для выполнения процедуры (*) можно обойтись O(N) операциями. Для этого заметим, что за один поиск значения (*) к множеству Q_n добавляется всего одна точка и, поэтому, на следующем шаге значения l_x изменятся только у вершин, смежных этой новой точке. Т.о. для пересчета в (*) всех значений l_x требуется пересчитать l_x только для точек, смежных одной точке, полученной при предыдущем выполнении (*). В силу введенных предположений, это можно сделать за O(N) операций. Искать же минимум l_x можно по всем вершинам графа, не принадлежащим Q_n, что тоже требует O(N) операций. Т.о. процедуру (*) можно реализовать за O(N) операций.

Для реализации алгоритма Дейкстры следует добавить в каждую вершину w графа вещественное число l_w, характеризующее длину кратчайшего пути от вершины a до вершины w и логическую переменную s_w, указывающую – посчитана ли на данный момент эта кратчайшая длина пути.

Для упрощения дальнейшей жизни (т.е. для поиска, собственно, кратчайшего пути при определенных значения l_w) можно в каждом элементе также хранить ссылку на вершину, из которой мы в данную вершину пришли. Для текущей вершины w будем эту ссылку называть back_w. Т.о. элементы Q_i представляются в виде q=(w, l_w, s_w, back_w).

Будем предполагать, что конкретная техника нам позволяет инициализировать все l_w значением = плюс бесконечность (+INF), что мы и сделаем. Инициализируем все s_w значением = FALSE.

Введем переменную c, которая будет хранить последнюю вершину, добавленную в множество вершин с найденной минимальной длиной пути до вершины. Тогда алгоритм будет выглядеть следующим образом

Дата добавления: 2015-10-30