АЛГОРИТМ ДЕЙКСТРА ПОИСКА КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ

Дан граф G = (X, А, С) со взвешенными дугами, пример которого показан на рис. 61.1. Обозначим Цх,) пометку вершины х,-. Веса дуг (или ребер) даны матрицей весов.

Граф со взвешенными дугами Матрица весов расстояний имеет вид

Рис. 61.1. Граф со взвешенными дугами Матрица весов расстояний имеет вид:

Рассмотрим алгоритм нахождения кратчайшего пути от вершины s к вершине t графа и более общий случай: от вершины s ко всем вершинам графа.

Присвоение начальных значений

Шаг 1. Положить L(s) = 0 и считать эту пометку постоянной. Для всех вершин х ,Ф s положить Цх,) = оо и считать эти пометки временными. За текущую рассматриваемую вершину с постоянной пометкой возьмем вершину р, т.е. положим р = s.

Обновление пометок

Шаг 2. Для вершин, входящих в прямое отображение вершины р, т.е. для всех х,-, принадлежащих Г(р), пометки которых временные, изменить пометки в соответствии со следующим выражением:

Цх,) = min [Цх,), L(p) + C(p, x,)].

Превращение пометки в постоянную

Шаг 3. Среди всех вершин с временными пометками найти такую, для которой

L(Xi*) = min [!(#)].

Шаг 4. Считать пометку вершины х,* постоянной и положить р = х,*.

Шаг 5(a). {При нахождении пути от s к t)

  • - Если текущая вершина р является искомой, т.е. р = t, то Lip) является длиной кратчайшего пути от s к t. Стоп.
  • - Еслирф(, перейти к шагу 2.

Шаг 5(6). {При нахождении путей от s ко всем вершинам}

  • - Если все вершины отмечены постоянными метками, то эти метки дают длины кратчайших путей.
  • - Если некоторые метки являются временными, то следует перейти к шагу 2.

Как только длины кратчайших путей от вершины s будут найдены, сами пути можно получить с помощью рекурсивной процедуры (61.1):

L(x*)+c(x*,xi) = L(xi). (61.1)

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

Пример. Рассмотрим граф смешанного типа, изображенный на рис. 61.2, а, где каждое неориентированное ребро рассматривается как пара противоположно направленных дуг равного веса. Матрица весов приведена на рис. 61.2, б. Требуется найти все кратчайшие пути от вершины xi ко всем остальным вершинам.

Первая итерация

Постоянные пометки будем помечать знаком «+».

Шаг 1. Присвоим Цх) = 0, Ь(х,) = оо для всех лс,-, кроме х. Положим Р =х.

Шаг 2. Найдем прямое отображение для текущей рассматриваемой вершины: Г(/?) = T(xi) = {хъ хъ *8, *9}- Все вершины, входящие в прямое отображение, имеют временные пометки, поэтому пересчитаем их значение: Пример поиска кратчайшего пути

Рис. 61.2. Пример поиска кратчайшего пути: а — граф; б—матрица весов дуг

Шаг 3. На данном шаге итерации имеем следующие временные метки вершин:

Очевидно, что минимальную метку, равную 3, имеет вершина лу.

Шаг 4. За следующую текущую метку принимаем вершину xj, т.е. р=X'j, а ее метка становится постоянной, Цх7) = 3+.

Шаг 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу 2.

Вторая итерация

Шаг 2. Находим Г(х7) = {хг, Х4, х& Х9}. Метки всех вершин временные, следовательно, пересчитываем их значения:

Шаг 3. На данном шаге итерации имеем следующие временные метки вершин:

Очевидно, что минимальную метку, равную 5, имеет вершина хг.

Шаг 4. За следующую текущую метку принимаем вершину хг, т.е. р=х2, а ее метка становится постоянной, Цхт) — 5+.

Шаг 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу 2.

Третья итерация

Шаг 2. Находим Г(хг) = {хь хз, хъ Х9}. Метки вершин хз и Х9 временные, следовательно, пересчитываем их значения:

Шаг 3. На данном шаге итерации имеем следующие временные метки вершин:

Очевидно, что минимальную метку, равную 6, имеет вершина xs.

Шаг 4. За следующую текущую метку принимаем вершину х$, т.е. р=х8, а ее метка становится постоянной, L(xg) = 6+.

Шаг 5. Не все вершины графа имеют постоянные метки, поэтому переходим к шагу 2.

Четвертая итерация

Шаг 2. Находим Г(хв) = {хь Х5, х& Х9}. Метки вершин Х5, хв и Х9 временные, следовательно, пересчитываем их значения:

Шаг 3. На данном шаге итерации имеем следующие временные метки вершин:

Очевидно, что минимальную метку, равную 7 имеет вершина хф

Шаг 4. За следующую текущую метку принимаем вершину Х4, т.е. р = Х4, а ее метка становится постоянной, L(x4) = 7+.

Шаг 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу 2.

Пятая итерация

Шаг 2. Находим Г(х4) = {хз, Х5, Хб, Х7}. Метки вершин хз, Х5 и Хб временные, следовательно, пересчитываем их значения:

Шаг 3. На данном шаге итерации имеем следующие временные метки вершин:

Очевидно, что минимальную метку, равную 11, имеет вершинах^

Шаг 4. За следующую текущую метку принимаем вершину х% т.е. р — Хд, а ее метка становится постоянной, Цх9) =11+.

Шаг 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу 2.

Шестая итерация

Шаг 2. Находим Метка вершины х6 временная, следовательно, пересчитываем ее значение:

Шаг 3. На данном шаге итерации имеем следующие временные метки вершин:

Очевидно, что минимальную метку, равную 12, имеет вершина Х5.

Шаг 4. За следующую текущую метку принимаем вершину Х5 , т.е. р = х5, а ее метка становится постоянной, L(xs) = 12+.

Шаг 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу 2.

Седьмая итерация

Шаг 2. Находим Метка вершины хв временная, следовательно, пересчитываем ее значение:

Шаг 3. На данном шаге итерации имеем следующие временные метки:

Очевидно, что минимальную метку, равную 17, имеет вершина Хб.

Шаг 4. За следующую текущую метку принимаем вершину *6, т.е. р=х6, а ее метка становится постоянной, Цхв) = 17+.

Шаг 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу 2.

Восьмая итерация

Шаг 2. Находим . Метка вершины хз временная, следовательно, пересчитываем ее значение:

Шаг 3. На данном шаге итерации имеем одну временную метку вершины: Цхз) = 23, которая становится постоянной.

Шаг 4. Все вершины имеют постоянные метки, поэтому алгоритм окончен.

Для нахождения кратчайшего пути между вершинами, например, Х2 и начальной х последовательно используем соотношение (61.2):

где вершинахг — это вершина, непосредственно предшествующая хг в кратчайшем пути otjcj к хг.

Единственной такой вершиной является вершина xj. Далее соотношение (61.2) применяем второй раз:

Единственной такой вершиной является вершина х. Поэтому кратчайший путь от х к Х2 есть (хь Хъ Х2).

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >