Алгоритм, предложенный Р. Примом, состоит в выполнении следующих операций:

1. Вершине-входу присваиваем потенциал  ₁ = 0; остальным вершинам – потенциал  _i = , i = 1…n, где n - число вершин в рассматриваемом графе.

2. Для каждой вершины i, смежной с вершиной j из массива вершин L, находим  _j + l (j, i) и проверяем неравенство

 _j + l (j, i) <  _i.

Если неравенство выполняется, то

.

Вершину i заносим в массив L₁.

1. Проверяем массив . Если неравенство выполняется , осуществляем переход к п. 2.

2. Конец алгоритма нахождения кратчайших путей.

Рассмотрим работу алгоритма на примере.

Пример

Допустим, имеется граф (рис. 17), представленный списком дуг:

Рис. 17

(1,2) – 3

(1,3) – 9

(2,3) – 5

(3,4) – 1

(4,5) – 2

(4,6) – 6

(3,5) – 2

(5,2) – -1

(5,6) – 4

(6,0) – 0

Решение:

Результаты работы алгоритма по шагам вычислений сведем в таблицу.

Шаг вычислений	Массив L	Потенциалы вершин						Массив L1
		1	2	3	4	5	6
0		0						1
1	1	0	3	9				2, 3
2	2, 3	0	3	8	10	11		3, 4, 5
3	3, 4, 5	0	3	8	9	10	15	4, 5, 6
4	4, 5, 6	0	3	8	9	10	14	6
5	6	0	3	8	9	10	14

На нулевом шаге производится инициализация согласно п.1 алгоритма. Далее на первом шаге вычислений рассматриваются вершины, смежные с вершиной-входом, потенциалы рассматриваемых вершин становятся равными длине соединяющей их дуги, если таковое существует, в противном случае – потенциал вершины остается равным .

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

1. 1 – 3 – 4 – 6: потенциал вершины 6 изменяется  ₆ = 16;

2. 1 – 2 – 3 – 5: потенциал вершины 5 изменяется  ₅ = 10;

3. 1 – 3 – 5 – 2: потенциал вершины 2 не изменится ( ₂ < 10);

4. 1 – 3 – 4 – 5: потенциал вершины 5 не изменится ( ₅ < 12);

5. 1 – 3 – 5 – 6: потенциал вершины 6 изменится  ₆ = 15.

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

1. 1 – 2 – 3 – 5 – 6: потенциал вершины 6 изменится  ₆ = 14;

2. 1 – 2 – 3 – 4 – 5: потенциал вершины 5 не изменится ( ₅ < 11);

3. 1 – 2 – 3 – 5 – 2: потенциал вершины 2 не изменится ( ₂ < 9);

4. 1 – 3 – 5 – 2 – 3: потенциал вершины 3 не изменится ( ₃ < 15);

5. 1 – 3 – 4 – 5 – 2: потенциал вершины 2 не изменится ( ₂ < 11).

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

1. 1 – 3 – 5 – 2 – 3 – 5: потенциал вершины 5 не изменится ( ₅ < 17);

2. 1 – 3 – 5 – 2 – 3 – 4: потенциал вершины 4 не изменится ( ₄ < 16);

3. 1 – 3 – 4 – 5 – 2 – 3: потенциал вершины 3 не изменится ( ₃ < 14);

4. 1 – 2 – 3 – 4 – 5 – 2: потенциал вершины 2 не изменится ( ₂ < 10);

5. 1 – 2 – 3 – 4 – 5 – 6: потенциал вершины 6 не изменится ( ₆ = 14);

6. 1 – 2 – 3 – 5 – 2 – 3: потенциал вершины 3 не изменится ( ₃ < 14).

На пятом шаге вычислений не произошло изменений ни в одном из потенциалов вершин графа, делаем вывод об окончании работы алгоритма.

Восстановим кратчайший путь из вершины 6 в вершину 1. Для этого для каждой вершины j определим такую вершину i, что будет выполняться правило

Следуя правилу, последовательно находим кратчайший путь:

вершина 6: i = 5; вершина 5: i = 3; вершина 3: i = 2; вершина 2: i = 1.

Кратчайшим путем (рис. 18) является путь 1 – 2 – 3 – 5 – 6.

Рис. 18

Задания

Дан список дуг с указанием их длин. Составьте по нему рисунок ориентированного графа. Найдите для этого графа наименьший путь от вершины-входа до вершины с максимальным номером.

1. (0;1) – 3, (0;2) – 9, (1;2) – 5,

(2;4) – 1, (1;3) – 8, (2;3) – 2,

(3;5) – 4, (4;5) – 6.

1. (0;1) – 4, (0;2) – 5, (1;2) – 8,

(2;4) – 3, (1;3) – 11, (2;3) – 5,

(3;5) – 3, (4;5) – 6.

1. (0;1) – 3, (0;2) – 9, (1;2) – 12, (2;4) – 1, (1;3) – 2, (2;3) – 3,

(3;5) – 10, (4;5) – 5.

1. (0;1) – 6, (0;2) – 2, (2;1) – 3,

(2;4) – 6, (1;3) – 1, (2;3) – 5,

(3;5) – 8, (4;5) – 7.

1. (0;1) – 6, (0;2) – 5, (1;2) – 1,

(2;4) – 6, (1;3) – 7, (2;3) – 6,

(3;5) – 8, (4;5) – 7.

1. (0;1) – 3, (0;2) – 2, (2;1) – 1,

(2;5) – 3, (1;5) – 4, (5;4) – 8,

(5;3) – 5, (3;4) – 3, (4;6) – 2,

(3;6) – 4.

1. (0;1) – 10, (0;2) – 5, (2;1) – 4, (2;5) – 8, (1;5) – 3, (5;4) – 4,

(5;3) – 2, (3;4) – 1, (4;6) – 5,

(3;6) – 7.

1. (0;1) – 3, (0;2) – 2, (2;1) – 2,

(2;5) – 12, (1;5) – 8, (5;4) – 2,

(5;3) – 6, (3;4) – 1, (4;6) – 8,

(3;6) – 3.

1. (0;1) – 2, (0;2) – 7, (2;1) – 1,

(2;5) – 6, (1;5) – 12, (5;4) – 10,

(5;3) – 5, (3;4) – 4, (4;6) – 2,

(3;6) – 7.

1. (0;1) – 4, (0;2) – 2, (2;1) – 1,

(2;5) – 7, (1;5) – 5, (5;4) – 4,

(5;3) – 1, (3;4) – 4, (4;6) – 3,

(3;6) – 7.

1. (0;2) – 2, (0;1) – 7, (2;1) – 4,

(2;4) – 9, (1;3) – 3, (3;4) – 1,

(4;6) – 2, (3;5) – 8, (6;5) – 4,

(6;7) – 10, (5;7) – 5.

1. (0;2) – 10, (0;1) – 5, (2;1) – 1, (2;4) – 4, (1;3) – 3, (3;4) – 5,

(4;6) – 3, (3;5) – 10, (6;5) – 10,

(6;7) – 5, (5;7) – 1.

1. (0;2) – 4, (0;1) – 6, (2;1) – 4,

(2;4) – 6, (1;3) – 3, (3;4) – 2,

(4;6) – 4, (3;5) – 7, (6;5) – 3,

(6;7) – 8, (5;7) – 5.

1. (0;2) – 3, (0;1) – 1, (2;1) – 4,

(2;4) – 2, (1;3) – 6, (3;4) – 4,

(4;6) – 3, (3;5) – 6, (6;5) – 4,

(6;7) – 12, (5;7) – 7.

1. (0;2) – 8, (0;1) – 12, (2;1) – 3, (2;4) – 6, (1;3) – 5, (3;4) – 4,

(4;6) – 10, (3;5) – 4, (6;5) – 6,

(6;7) – 10, (5;7) – 6.

1. (0;1) – 3, (0;2) – 3, (1;4) – 3,

(2;5) – 3, (1;3) – 2, (0;3) – 4,

(2;3) – 2, (3;4) – 2, (3;6) – 4,

(3;5) – 2, (4;6) – 3, (5;6) – 3.

1. (0;1) – 3, (0;2) – 2, (1;4) – 13, (2;5) – 13, (1;3) – 7, (0;3) – 11, (2;3) – 9, (3;4) – 5, (3;6) – 10, (3;5) – 3, (4;6) – 4, (5;6) – 7.

2. (0;1) – 4, (0;2) – 5, (1;4) – 7,

(2;5) – 7, (1;3) – 5, (0;3) – 8,

(2;3) – 4, (3;4) – 2, (3;6) – 7,

(3;5) – 1, (4;6) – 4, (5;6) – 6.

1. (0;1) – 5, (0;2) – 5, (1;4) – 4,

(2;5) – 5, (1;3) – 3, (0;3) – 10,

(2;3) – 3, (3;4) – 3, (3; 6) – 10,

(3;5) – 3, (4;6) – 7, (5;6) – 5.

1. (0;1) – 6, (0;2) – 7, (1;4) – 18, (2;5) – 19, (1;3) – 8, (0;3) – 14, (2;3) – 6, (3;4) – 8, (3;6) – 14, (3;5) – 5, (4;6) – 5, (5;6) – 9.

2. (0;1) – 2, (1;2) – 3, (0;2) – 6,

(2;3) – 4, (3;4) – 2, (2;4) – 7,

(4;5) – 5, (5;6) – 3, (4;6) – 9.

1. (0;1) – 3, (1;2) – 5, (0;2) – 7,

(2;3) – 6, (3;4) – 5, (2;4) – 12,

(4;5) – 3, (5;6) – 2, (4;6) – 4.

1. (0;1) – 5, (1;2) – 4, (0;2) – 10, (2;3) – 4, (3;4) – 5, (2;4) – 8,

(4;5) – 7, (5;6) – 6, (4;6) – 14.

1. (0;1) – 2, (1;2) – 4, (0;2) – 5,

(2;3) – 4, (3;4) – 5, (2;4) – 8,

(4;5) – 3, (5;6) – 2, (4;6) – 4.

1. (0;1) – 3, (1;2) – 2, (0;2) – 5,

(2;3) – 1, (3;4) – 1, (2;4) – 3,

(4;5) – 2, (5;6) – 2, (4;6) – 3.

1. (0;1) – 10, (0;2) – 4, (1;4) – 8, (2;5) – 20, (3;1) – 5, (4;3) – 3, (2;3) – 4, (3;5) – 17, (4;6) – 7, (5;6) – 5.

2. (0;1) – 6, (0;2) – 2, (1;4) – 4,

(2;5) – 15, (3;1) – 2, (4;3) – 3,

(2;3) – 13, (3;5) – 2, (4;6) – 7,

(5;6) – 1.

1. (0;1) – 2, (0;2) – 3, (1;4) – 1,

(2;5) – 10, (3;1) – 1, (4;3) – 6,

(2;3) – 4, (3;5) – 5, (4;6) – 20,

(5;6) – 6.

1. (0;1) – 2, (0;2) – 3, (1;4) – 7,

(2;5) – 6, (3;1) – 1, (4;3) – 2,

(2;3) – 2, (3;5) – 3, (4;6) – 8,

(5;6) – 10.

1. (0;1) – 3, (0;2) – 7, (1;4) – 8,

(2;5) – 3, (3;1) – 1, (4;3) – 4,

(2;3) – 2, (3;5) – 2, (4;6) – 7,

(5;6) – 6.

Алгоритм Дейкстра

Описание алгоритма

Алгоритм Дейкстра требует, чтобы длины всех дуг были положительны. Объем вычислений в худшем случае для этого алгоритма значительно меньше, чем у алгоритма Беллмана – Форда. Основная его идея состоит в том, чтобы отыскивать кратчайшие пути в порядке возрастания длины пути. Кратчайшим среди всех кратчайших путей от вершины-входа является путь, состоящий из одной дуги, соединяющий вершину-вход с ближайшей соседней вершиной, так как любой путь, состоящий из нескольких дуг, будет всегда длиннее первой дуги вследствие предположения о положительности всех дуговых длин. Следующим кратчайшим среди кратчайших путей должен быть либо путь из одной дуги к следующему ближайшему соседу вершины-входа, либо кратчайший путь из двух дуг, проходящий через вершину, выбранный на первом шаге и т.д. Алгоритм Дейкстра состоит в выполнении следующих операций:

Шаг 0. Помечаем нулевую вершину индексом λ₀ = 0.

Шаг k. Пусть уже помечено некоторое количество вершин. Обозначим Q множество непомеченных вершин, смежных с помеченными. Для каждой вершины k принадлежащей Q вычисляем величину ξ_k = min ( λ_k + l_ki ), где минимум берется по всем помеченным вершинам i, смежным с вершиной k. Помечаем вершину k, для которой величина ξ_k минимальна, индексом λ_k = ξ_k . Подобную процедуру повторяем до тех пор, пока не будет помечена вершина n. Длина кратчайшего пути равна λ_n, а сам кратчайший путь определяется так, как это было описано выше.

Пример