Материал: Решение задач теории графов методические указания к практическим занятиям по дисциплине «Дискретная математика». Белецкая С.Ю

(s..., Qⁿ(t)..., Q(Q(t)), Q(t),t),

Qⁿ(t)= Q(Q(...Q(t)) (n раз).

Перед началом работы алгоритма начальная вершина s имеет постоянную метку l(s)=0, а метки всех остальных вершин равны бесконечности (∞) и являются временными. Обозначим через p последнюю из вершин, получивших постоянную метку.

Алгоритм Дейкстры включает следующие шаги:

1. Положить l(s)=0 и считать эту метку постоянной. Положить l(x_i)= ∞ для всех x_i  s, и считать эти метки временными. p = s.

2. Обновление пометок. Для всех вершин x_i  Г(p), пометки которых временные, изменить пометки в соответствии с правилом:

l(x_i)=min { l(x_i), l(p) +w(p, x_i) }.

Если l(x_i)> l(p) +w(p, x_i), то Q(x_i) = p.

3. Если l(x_i)= ∞ для всех вершин x_i, пометки которых временные, то в исходном графе отсутствуют пути из вершины s в вершины с временными метками. Останов алгоритма. В противном случае переход к шагу 4.

4. Превращение пометок в постоянные. Среди всех вершин с временными метками найти такую вершину x_i^* , для которой l(x_i^*) = minl(x_i) (метка минимальная) и считать эту пометку постоянной. Положить p=x_i^*. Пометку Q(x_i^*) также считать постоянной.

5. Если p  t, перейти к шагу 2, а если p = t, то l(p) - длина кратчайшего пути из s в t.

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

5.2. Пример

Для взвешенного орграфа найти кратчайший путь из вершины s в вершину t.

Рис. 17

1. Помечаем в соответствии с алгоритмом вершины графа:

l(s) = 0 ,

l(a) = ∞ ,

l(b) = ∞ ,

l(c) = ∞ ,

l(d) = ∞ ,

l(t) = ∞ .

Вершине s приписываем постоянную пометку, т.е. p = s.

2. Из вершины s помечаем остальные вершины:

l(a) = min {∞, 0 + 4} = 4,

l(b) = min {∞, 0 + 7} = 7,

l(c) = min {∞, 0 + 3} = 3,

l(d) = ∞ ,

l(t) = ∞ .

У вершин a, b, и с уменьшились пометки, следовательно

Q(a) = s, Q(b) = s, Q(c) = s.

Вершине c приписываем постоянную пометку, т.е. p = c. Пометка Q(с)=s также становится постоянной.

3. Из вершины c помечаем остальные вершины:

l(a) = min {4, 3 + ∞} = 4,

l(b) = min {7, 3 + ∞} = 7,

l(d) = min {∞, 3 + 3} = 6,

l(t) = ∞ .

У вершины d уменьшилась пометка, следовательно Q(d) = c.

Вершине a приписываем постоянную пометку, т.е. p = a. Пометка Q(a)=s становится постоянной.

4. Из вершины а помечаем остальные вершины:

l(b) = min {7, 4 + 4} = 7,

l(d) = min {6, 4 + 3} = 6,

l(t) = ∞ .

Вершине d приписываем постоянную пометку, т.е. p = d.. Пометка Q(d)=c становится постоянной.

5. Из вершины d помечаем остальные вершины:

l(b) = min {7, 6 + ∞} = 7,

l(t) = min {∞, 6 + 2} = 8,

У вершины t уменьшилась пометка, следовательно Q(t) = d.

Вершине b приписываем постоянную пометку, т.е. p=b. Пометка Q(b)=s становится постоянной.

6. Из вершины b помечаем вершину t:

l(t) = min {8, 7 + 2} = 8.

Метки l(t) и Q(t)=d становятся постоянными.

7. Восстанавливаем по меткам Q кратчайший путь из s в t:

Путь scdt длиной 8.

Работу алгоритма можно проиллюстрировать таблицей:

5.3. Упражнения

Определить кратчайший путь от вершины s до вершины t с использованием алгоритма Дейкстры.

а б

в г

д е

ж з

Рис. 18

6. Определение кратчайших путей между всеми парами вершин графа. Алгоритм флойда

6.1. Теоретические сведения

Алгоритм Флойда  это алгоритм поиска кратчайших путей между всеми вершинами парами вершин графа .

Пусть дан взвешенный орграф с n вершинами и матрицей весов W. Каждый элемент матрицы весов w_ij равен весу дуги < x_i, x_j > (если такой дуги нет, то w_ij=∞ ), а w_ii = 0  i =1...n.

Предположим, что граф не содержит контуров отрицательной длины. Пронумеруем вершины графа от 1 до n. Обозначим W^k матрицу с элементами w_ij^k, каждый из которых равен длине кратчайшего пути из вершины i в вершину j, который может содержать в качестве промежуточных вершин только первые k вершин графа. Если такого пути не существует, то w_ij = ∞. W⁰=W. По матрице W⁰ вычисляется матрица W¹ и т.д. до тех пор, пока не будет определена матрица Wⁿ , cодержащая кратчайшие пути между всеми вершинами графа. Элементы матрицы W^k на k-й итерации вычисляются следующим образом:

w^k _ij = min{w_ik^k-1 + w_kj^k-1, w_ij^k-1} ,

где w_ik^k-1 - длина кратчайшего пути из вершины i в вершину k, в которой в качестве промежуточных используются первые k-1 вершины графа.

Для того, чтобы по окончании работы алгоритма можно было быстро построить кратчайший путь, на каждой итерации вместе с матрицей W^k строится матрица P^k, каждый элемент которой p^k_ij равен номеру вершины, предшествующей вершине j в текущем ij пути.

На первой итерации

p⁰_ij=i ,  i,j = 1...n и i  j,

p⁰_ii=0 ,  i = 1...n.

Номера вершин, включаемых в кратчайший путь, определяются следующим образом:

(i ,..., j₃, j₂, j₁, j),

j₁=p_ij ⁿ

j₂=p_ij1 ⁿ и т.д.

Основные шаги алгоритма:

1. Пронумеровать вершины графа целыми числами. k=0. Определить матрицу W⁰. Определить матрицу P⁰, p⁰_ij=i,  i  j, i,j=1...n и p⁰_i,i=0,  i = j =1...n.

2. Если k = n, работа алгоритма закончена (Wⁿ - эта матрица весов кратчайших путей между всеми парами вершин графа, определяемых с помощью матрицы Pⁿ). Если k  n, то k = k+1, переход к шагу 3.

3. Вычислить для всех i,j = 1...n элементы

w^k _ij =min{w_ik^k-1 + w_kj^k-1, w_ij^k-1}.

Если w_ij^k-1 < w_ik^k-1 + w_kj^k-1 , то p^k_{ij =} p^k-1_ij . Иначе p^k_{ij =} p^k-1_kj.

4. Если для некоторого 1≤ q ≤ n элемент с w_qq^k < 0, то в графе имеется контур отрицательной длины и работа алгоритма завершается. Иначе перейти к шагу 2.

6.2. Пример

Дан взвешенный орграф G, который содержит положительные и отрицательные веса. Найти кратчайшие пути между всеми вершинами графа.

Рис. 19

Решение

Пронумеруем вершины графа целыми числами (1, 2, 3, и 4) и определим матрицы W⁰ и P⁰:

Согласно алгоритму определяем матрицы W¹ и P¹.

W² и P² :

W³ и P³ :

W⁴ и P⁴ :

Таким образом, мы получили матрицу весов кратчайших путей W⁴ между всеми вершинами графа. Определяем их с помощью матрицы P⁴.

Кратчайшие пути между вершинами:

1 и 2: L(1, 2) = -2, путь : 1-2;

1 и 3: L(1, 3) = 0, путь : 1-2-3;

1 и 4: L(1, 4) = -3, путь : 1-4;

2 и 1: L(2, 1) = 3, путь : 2-3-4-1;

2 и 3: L(2, 3) = 2, путь : 2-3;

2 и 4: L(2, 4) = -1, путь : 2-3-4;

3 и 1: L(3, 1) = 1, путь : 3-4-1;

3 и 2: L(3, 2) = -1, путь : 3-4-1-2

3 и 4: L(3, 4) = -3, путь : 3-4;

4 и 1: L(4, 1) = 4, путь : 4-1;

4 и 2: L(4, 2) = 2, путь : 4-1-2;

4 и 3: L(4, 3) = 4, путь : 4-1-2-3;