1.1. Теоретическое описание метода Дейкстры

Пусть — взвешенный граф, где— множество вершин графа,;— множество ребер графа. Веса дуг имеют положительные значения.

Граф задан матрицей весов дуг размера.

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

Начальную и конечную вершины обозначим соответственно и. — маршрут минимального веса будем называть кратчайшим -маршрутом.

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

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

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

Постоянные метки не меняют своего значения до конца алгоритма.

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

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

если вершина непосредственно предшествуетв кратчайшем-маршруте, то для неё выполняется соотношение

.

На подготовительном (нулевом) шаге начальной вершине присваивается окончательная метка, а всем остальным вершинам() временные метки.

Общий -й шаг состоит в следующем. Вершину, получившую постоянную метку на предыдущем -шаге будем обозна­чать. Вершины, являющиеся образами вершины, будем обозначать.

Вершины имеют временные метки. Для них производится пересчет значений меток в соответствии с формулой

,

где -вeca дуг, соединяющих вершину , получившую окончательную метку на предыдущем шаге, с ее «детьми».

Метки остальных вершин остаются без изменений.

Среди всех вершин с временными метками находится вершина , имеющая минимальную метку

.

На каждом шаге определяется множество вершин , получивших окончательные метки,– множество вершин, имеющих временные метки.

Метка вершины считается постоянной и принимается.

Тогда

; .

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

Метка — вес кратчайшего-маршрута.

Этот маршрут определяется с помощью меток :

,

где для любой вершины графа.

Формальное описание алгоритма имеет вид.

1. Положить и считать эту метку постоянной. Положитьдля всех,;;.

2. Для всех с временными метками пересчитать метки по формуле:

.

3. Множество вершин с временными метками .

Среди вершин с временными метками найти такую, что

.

Считать метку постоянной.

Присвоить ;;.

4. Если , то перейти к п. 5.

–вес кратчайшего маршрута. Иначе положить и перейти к п.2

5. Кратчайший маршрут определяется метками :

.

Конец.