Алгоритм Дейкстра поиска кратчайших путей в графе

Разбить на страницы

Показывать лекцию целиком

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

Дан граф Обозначим L(х_i) пометку вершины х_i. Веса дуг (или ребер) даны матрицей весов ().

(рис 9.1) Граф со взвешенными дугами

Матрица весов расстояний
с₁	с₃
	с₂
		с₅
с₄

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

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

Ш А Г 1. Положить L(s) = 0 и считать эту пометку постоянной. Для всех вершин $$х_{i} \ne s$$ положить $$L(х_{i})= \infty$$ и считать эти пометки временными. За текущую рассматриваемую вершину с постоянной пометкой возьмем вершину p, т. е. положить p = s.

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

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

L(х_i) <- min [ L(х_i), L(p) + C(p, х_i) ].

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

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

L(x^*_i)=min[L(x_i)].

Ш А Г 4. Считать пометку вершины x^*_i постоянной и положить p=x^*_i.

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

Если текущая вершина p является искомой, т. е. p = t, то L(p) является длиной кратчайшего пути от s к t. Останов.

Если $$p \ne t$$, перейти к шагу 2.

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

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

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

Как только длины кратчайших путей от вершины s будут найдены, сами пути можно получить с помощью рекурсивной процедуры ( * ). Так как вершина x^*_i непосредственно предшествует вершине х_i в кратчайшем пути от s к х_i, то для любой вершины х_i соответствующую вершину x^*_i можно найти как одну из оставшихся вершин, для которой

L(x^*_i)+c( x^*_i, x_i)=L( x_i).(*)

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

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

(рис 9.2) Пример поиска кратчайшего пути: а – граф; б – матрица весов дуг

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

Ш А Г 1. Присвоим $$L(х_{1}) = 0, L(х_{i}) = \infty$$ для всех х_i, кроме х₁. Положим р = х₁.

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

Ш А Г 2. Найдем прямое отображение для текущей рассматриваемой вершины: Г(р) = Г(х₁) = { х₂, х₇, х₈, х₉ }. Все вершины, входящие в прямое отображение имеют временные пометки, поэтому пересчитаем их значение:

$$L(x_{2})=min[L(x_{2}),L(x_{1}) + c(x_{1},x_{2})]=min[\infty ,0+10]=10$$

$$L(x_{7})=min[\infty ,0+3]=3$$

$$L(x_{8})=min[\infty ,0+6]=6$$

$$L(x_{9})=min[\infty ,0+12]=12$$

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

$$L(х_{2}) = 10, L(х_{3}) = \infty$$,

$$L(х_{7}) = 3, L(х_{4}) = \infty$$,

$$L(х_{8}) = 6, L(х_{5}) = \infty$$,

$$L(х_{9}) = 12, L(х_{6}) = \infty$$.

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

Ш А Г 4. За следующую текущую метку принимаем вершину х₇, т. е. p = х₇, а ее метка становится постоянной, L(х₇) = 3⁺.

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

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

Граф с текущими значениями меток вершин показан на

(рис 9.3) Пометки в конце первой итерации

Ш А Г 2. Находим Г(х₇) = { х₂, х₄, х₆, х₉}. Метки всех вершин временные, следовательно пересчитываем их значения:

L(х₂)= min [10, 3 + 2 ] = 5,

$$L(х_{4})= min [ \infty , 3 + 4 ] = 7$$,

$$L(х_{6})= min [ \infty , 3 + 14 ] = 17$$,

L(х₉)= min [ 12, 3 + 24 ] = 12.

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

$$L(х_{2}) = 5, L(х_{3}) = \infty$$,

$$L(х_{4}) = 7, L(х_{5}) = \infty$$,

L(х₆) = 17, L(х₈) = 6, L(х₉) = 12.

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

Ш А Г 4. За следующую текущую метку принимаем вершину х₂, т. е. p = х₂, а ее метка становится постоянной, L(х₂) = 5⁺.

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

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

Граф с текущими значениями меток вершин показан на .

(рис 9.4) Пометки в конце второй итерации

Ш А Г 2. Находим Г(х₂) = {х₁, х₃, х₇, х₉}. Метки вершин х₃ и х₉ временные, следовательно пересчитываем их значения:

$$L(х_{3}) = min [ \infty , 5 + 18 ] = 23$$,

L(х₉) = min [ 12, 5+13 ] = 12.

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

$$L(х_{3}) = 23, L(х_{4}) = 7, L(х_{5}) = \infty$$,

L(х₆) = 17, L(х₈) = 6, L(х₉) = 12.

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

Ш А Г 4. За следующую текущую метку принимаем вершину х₈, т. е. p = х₈, а ее метка становится постоянной, L(х₈) = 6⁺.

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

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

Ш А Г 2. Находим Г(х₈) = { х₁, х₅, х₆, х₉ }. Метки вершин х₅, х₆ и х₉ временные, следовательно, пересчитываем их значения:

$$L(х_{5}) = min [ \infty , 6 + 23 ] = 29$$,

L(х₆) = min [ 17, 6 + 15 ] = 17,

L(х₉) = min [ 12, 6 + 5 ] = 11.

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

L(х₃) = 23, L(х₄) = 7,

L(х₅) = 29, L(х₆) = 17, L(х₉) = 11.

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

Ш А Г 4. За следующую текущую метку принимаем вершину х₄, т. е. p = х₄ , а ее метка становится постоянной, L(х₄) = 7⁺.

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

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

Ш А Г 2. Находим Г(х₄) = { х₃, х₅, х₆, х₇ }. Метки вершин х₃, х₅ и х₆ временные, следовательно, пересчитываем их значения:

L(х₃) = min [ 23, 7 + 25 ] = 23,

L(х₅)= min [ 29, 7 + 5 ] = 12,

L(х₆)= min [17, 7 + 16] = 17.

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

L(х₃) = 23, L(х₅) = 12,

L(х₆) = 17, L(х₉) = 11.

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

Ш А Г 4. За следующую текущую метку принимаем вершину х₉, т. е. p = х₉, а ее метка становится постоянной, L(х₉) = 11⁺.

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

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

Ш А Г 2. Находим Г(х₉) = {х₁, х₂, х₆, х₇, х₈}. Метка вершины х₆ временная, следовательно пересчитываем ее значение:

L(х₆) = min [17, 11 + 9] = 17.

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

L(х₃) = 23, L(х₅) = 12, L(х₆) = 17.

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

Ш А Г 4. За следующую текущую метку принимаем вершину х₅, т. е. p = х₅, а ее метка становится постоянной, L(х₅) = 12⁺.

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

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

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

L(х₆)= min [17, 12 + 10 ] = 17.

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

L(х₃) = 23, L(х₆) = 17.

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

Ш А Г 4. За следующую текущую метку принимаем вершину х₆, т. е. p = х₆, а ее метка становится постоянной, L(х₆) = 17⁺.

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

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

Ш А Г 2. Находим Г(х₆) = { х₃, х₅, х₇, х₈, х₉ }. Метка вершины х₃ временная, следовательно, пересчитываем ее значение:

L(х₃) = min [ 23, 17 + 20 ] = 23.

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

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

Для нахождения кратчайшего пути между вершинами, например, х₂ и начальной х₁ последовательно используем соотношение ( ** ): L(x^'₂)+c(x^'₂,x₂)=L(x₂)=5, где вершина x^'₂ – это вершина, непосредственно предшествующая х₂ в кратчайшем пути от х₁ к х₂.

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

L(x₇')+ с(x₇’, x₇) = L(x₇) = 3

Единственной такой вершиной является вершина х₁. Поэтому кратчайший путь от х₁ к х₂ есть ( х₁, х₇, х₂). Вершина х₁, называемая базой и дающая все кратчайшие пути от х₁ представляет дерево.

(рис 9.5) Окончательные пометки и х₁ - база

Страницы:

Дан граф Обозначим L(х_i) пометку вершины х_i. Веса дуг (или ребер) даны матрицей весов ().

(рис 9.1) Граф со взвешенными дугами

Матрица весов расстояний
с₁	с₃
	с₂
		с₅
с₄

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

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

L(х_i) <- min [ L(х_i), L(p) + C(p, х_i) ].

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

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

L(x^*_i)=min[L(x_i)].

Ш А Г 4. Считать пометку вершины x^*_i постоянной и положить p=x^*_i.

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

Если текущая вершина p является искомой, т. е. p = t, то L(p) является длиной кратчайшего пути от s к t. Останов.

Если $$p \ne t$$, перейти к шагу 2.

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

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

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

L(x^*_i)+c( x^*_i, x_i)=L( x_i).(*)

(рис 9.2) Пример поиска кратчайшего пути: а – граф; б – матрица весов дуг

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

Ш А Г 1. Присвоим $$L(х_{1}) = 0, L(х_{i}) = \infty$$ для всех х_i, кроме х₁. Положим р = х₁.

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

$$L(x_{2})=min[L(x_{2}),L(x_{1}) + c(x_{1},x_{2})]=min[\infty ,0+10]=10$$

$$L(x_{7})=min[\infty ,0+3]=3$$

$$L(x_{8})=min[\infty ,0+6]=6$$

$$L(x_{9})=min[\infty ,0+12]=12$$

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

$$L(х_{2}) = 10, L(х_{3}) = \infty$$,

$$L(х_{7}) = 3, L(х_{4}) = \infty$$,

$$L(х_{8}) = 6, L(х_{5}) = \infty$$,

$$L(х_{9}) = 12, L(х_{6}) = \infty$$.

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

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

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

Граф с текущими значениями меток вершин показан на

(рис 9.3) Пометки в конце первой итерации

L(х₂)= min [10, 3 + 2 ] = 5,

$$L(х_{4})= min [ \infty , 3 + 4 ] = 7$$,

$$L(х_{6})= min [ \infty , 3 + 14 ] = 17$$,

L(х₉)= min [ 12, 3 + 24 ] = 12.

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

$$L(х_{2}) = 5, L(х_{3}) = \infty$$,

$$L(х_{4}) = 7, L(х_{5}) = \infty$$,

L(х₆) = 17, L(х₈) = 6, L(х₉) = 12.

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

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

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

Граф с текущими значениями меток вершин показан на .

(рис 9.4) Пометки в конце второй итерации

$$L(х_{3}) = min [ \infty , 5 + 18 ] = 23$$,

L(х₉) = min [ 12, 5+13 ] = 12.

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

$$L(х_{3}) = 23, L(х_{4}) = 7, L(х_{5}) = \infty$$,

L(х₆) = 17, L(х₈) = 6, L(х₉) = 12.

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

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

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

$$L(х_{5}) = min [ \infty , 6 + 23 ] = 29$$,

L(х₆) = min [ 17, 6 + 15 ] = 17,

L(х₉) = min [ 12, 6 + 5 ] = 11.

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

L(х₃) = 23, L(х₄) = 7,

L(х₅) = 29, L(х₆) = 17, L(х₉) = 11.

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

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

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

L(х₃) = min [ 23, 7 + 25 ] = 23,

L(х₅)= min [ 29, 7 + 5 ] = 12,

L(х₆)= min [17, 7 + 16] = 17.

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

L(х₃) = 23, L(х₅) = 12,

L(х₆) = 17, L(х₉) = 11.

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

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

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

L(х₆) = min [17, 11 + 9] = 17.

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

L(х₃) = 23, L(х₅) = 12, L(х₆) = 17.

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

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

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

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

L(х₆)= min [17, 12 + 10 ] = 17.

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

L(х₃) = 23, L(х₆) = 17.

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

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

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

L(х₃) = min [ 23, 17 + 20 ] = 23.

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

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

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

L(x₇')+ с(x₇’, x₇) = L(x₇) = 3

(рис 9.5) Окончательные пометки и х₁ - база

Занятие пройдено

Предыдущее занятие Занятие пройдено Следующее занятие

Вернуться к учебному плану

Алгоритм Дейкстра поиска кратчайших путей в графе

Купить дополнительную попытку

Вы действительно хотите купить ещё одну попытку для прохождения тестирования?

Успешно!

Напишите нам, если у вас есть вопросы

Уважаемые пользователи ИНТУИТ!

Уважаемые пользователи ИНТУИТ!

Добро пожаловать на обновлённый сайт НОУ «ИНТУИТ»!