Числовые значения весов для вариантов №1-№15 приведены в таблице.
ПРИМЕР РЕШЕНИЯ ЗАДАЧИ
Для значений весов дуг
С12
С13
С14
С25
С27
С35
С36
С37
С45
С46
С47
С58
С59
С68
С69
С79
С8,10
С9,10
изобразим граф с указанием числовых значений весов дуг и направлением ориентации ребер.
С помощью алгоритма Дейкстры найдем длины наименьших путей, а также массив вершин предшественников на путях, из источника I – вершины 1 до каждой другой вершины графа, а также до стока – вершины 10.
Для этого нам понадобиться выполнить 9 итераций алгоритма. На каждой итерации будем определять очередную вершину с минимальной длиной пути до нее из источника и включать ее в множество вершин S – множество вершин, минимальные пути до которых нам известны к текущему моменту.
Шаг 1.
Включаем в S источник – вершину 1. Определим длины расстояний из источника до всех других вершин графа. Для всех вершин i, смежных с вершиной 1 положим длину пути из I в них, равной весу ребра их соединяющего С1i (). Для всех вершин, не смежных с вершиной 1 положим длину пути из I в них, равной ∞.
По условию задачи вершины смежные с I имеют номера 2, 3 и 4. Занесем данные в таблицу 1.
Таблица 1
S
D[2]
D[3]
D[4]
D[5]
D[6]
D[7]
D[8]
D[9]
D[10]
5
∞
∞
∞
∞
∞
∞
min(D[i]) = 5, i = 4
Полученные данные изобразим на графе. Вершины, включенные в S на каждом шаге, будем помечать желтым цветом (рис. 1), пути до вершин, которые возможно определить на текущем шаге алгоритма – зеленым, путь минимальной длинны на данном шаге – красным.
Рисунок 1.
Шаг 2.
По данным таблицы 1, минимальным является путь из источника в вершину 4 равный D[4] = 5, следовательно включаем в S вершину 4. Также заносим в вектор предшественников для вершины 4 значение 1, так как на кратчайшем пути из вершины 1 в вершину 4 вершиной предшествующей вершине 4 является вершина 1, т.е. сам источник: Prev[4] = 1.
Рисунок 2.
Имея в S вершины с номерами 1 и 4, определим минимальные длины путей, которые возможно построить из источника до других вершин графа проходя только через 1 и 4. Наличие вершины 4 в S не влечет появление путей в вершины 2 и 3 с более кратчайшим путем в них из источника, однако через вершины 1 и 4 есть возможность определить минимальный на текущем шаге путь до вершин 5, 6 и 7. Занесем данные в таблицу 2.
Таблица 2.
S
D[2]
D[3]
D[4]
D[5]
D[6]
D[7]
D[8]
D[9]
D[10]
5
∞
∞
∞
∞
∞
∞
1,4
7
min(5+7;∞)=12
min(5+5;∞)=10
min(5+2;∞)=7
∞
∞
∞
min(D[i])=7, i = 2
Шаг 3.
По данным таблицы 2 имеем две вершины с одинаковыми минимальными длинами путей до них из источника: вершины 2 и 7 с путями равными D[2] = D[7] = 7. На этом шаге мы можем включить в S любую из них, пусть это будет вершина 7. Для вершины 7 предшествующей на минимальном пути к ней будет вершина 4, следовательно Prev[7] = 4.
Рисунок 3.
Имея в S вершины с номерами 1, 4 и 7, пересчитаем длины путей, которые возможно построить из источника с помощью вершин множества S и выберем кратчайшие из них. С включением вершины 7 в S кратчайшие пути в вершины 2, 3, 5 и 6 не появляются, однако через вершины 1, 4 и 7 есть возможность определить минимальный на текущем шаге путь до вершины 9: D[9]= min(7+3;∞)=10. Данные занесем в таблицу 3.
Таблица 3.
S
D[2]
D[3]
D[4]
D[5]
D[6]
D[7]
D[8]
D[9]
D[10]
∞
∞
∞
∞
∞
∞
1,4
7
∞
∞
∞
1,4,7
7
∞
min(7+3;∞)=10
∞
min(D[i]) = 7, i = 2
Шаг 4.
На данном шаге кратчайшим из источника является путь в вершину 2 равный D[2] = 7, включим в S вершину 2. Для вершины 2 предшествующей на минимальном пути к ней является вершина 1, следовательно Prev[2] = 1.
Рисунок 4.
При включении в S вершины 2 появляется альтернативный путь из источника до вершины 5, пересчитаем будет ли он кратчайшим: D[5]= min(5+7;12)=12. До других вершин кратчайшие пути не возникают. Занесем данные в таблицу 4
Таблица 4.
S
D[2]
D[3]
D[4]
D[5]
D[6]
D[7]
D[8]
D[9]
D[10]
5
∞
∞
∞
∞
∞
∞
1,4
7
∞
∞
∞
1,4,7
7
∞
∞
1,4,7,2
8
min(5+7;12)=12
min(D[i]) = 8, i = 3
Шаг 5.
Кратчайшим из источника является путь в вершину 3 равный D[3] = 8, включим в S вершину 3. Для вершины 3 предшествующей на минимальном пути к ней является вершина 1, следовательно Prev[3] = 1.
Рисунок 5.
При включении в S вершины 3 появляется альтернативные пути из источника до вершин 5 и 6, пересчитаем будут ли они кратчайшими: D[5] = min(8+6;12) = 12, D[6] = min(8+7;10) = 10. До других вершин кратчайшие пути не возникают. Занесем данные в таблицу 5
Таблица 5.
S
D[2]
D[3]
D[4]
D[5]
D[6]
D[7]
D[8]
D[9]
D[10]
∞
∞
∞
∞
∞
∞
1,4
∞
∞
∞
1,4,7
∞
∞
1,4,7,2
∞
∞
1,4,7,2,3
min(8+6;12)=12
min(8+7;10)=10
∞
10
∞
min(D[i]) = 10, i = 9
Шаг 6.
По данным таблицы 5 имеем две вершины с одинаковыми минимальными длинами путей до них из источника: вершины 6 и 9 с путями равными D[6] = D[9] = 10. На этом шаге мы можем включить в S любую из них, пусть это будет вершина 9. Для вершины 9 предшествующей на минимальном пути к ней будет вершина 7, следовательно Prev[9] = 7.
Рисунок 6.
Включение вершины 9 в S не влечет появление путей в вершины 5 и 6 с более коротким путем в них из источника, однако наличие вершины 9 в S дает возможность определить минимальный на текущем шаге путь до вершины 10. Занесем данные в таблицу 6.
Таблица 5.
S
D[2]
D[3]
D[4]
D[5]
D[6]
D[7]
D[8]
D[9]
D[10]
∞
∞
∞
∞
∞
∞
1,4
∞
∞
∞
1,4,7
∞
∞
1,4,7,2
∞
∞
1,4,7,2,3
∞
∞
1,4,7,2,3,9
10
∞
min(10+3;∞)=13
min(D[i]) = 10, i = 6
Шаг 7.
На данном шаге алгоритма, кратчайшим из источника является путь в вершину 6 равный D[6] = 10, включим в S вершину 6, для которой предшествующей на минимальном пути является вершина 4: Prev[6] = 4. (Рис 6)
При включении в S вершины 6 становится возможным определить путь до вершины 8: D[8]=min(10+9;∞)=19. Длины путей до других вершин не пересчитываются. Занесем данные в таблицу 6.
Рисунок 6.
Таблица 6.
S
D[2]
D[3]
D[4]
D[5]
D[6]
D[7]
D[8]
D[9]
D[10]
∞
∞
∞
∞
∞
∞
1,4
∞
∞
∞
1,4,7
∞
∞
1,4,7,2
∞
∞
1,4,7,2,3
∞
∞
1,4,7,2,3,9
∞
1,4,7,2,3,9,6
12
min(10+9;∞)=19
min(D[i]) = 12, i = 5
Шаг 8.
На данном шаге алгоритма, кратчайшим из источника является путь в вершину 5: D[5] = 12. Вершину 6 включаем в S, предшествующей на минимальном пути для нее является вершина 2: Prev[5] = 2.
Рисунок 6.
При включении в S вершины 5 появляется альтернативный пути из источника до вершины 8, пересчитаем будут ли они кратчайшими: D[8] = min(8+6;12) = 12. Занесем данные в таблицу 7
Таблица 7.
S
D[2]
D[3]
D[4]
D[5]
D[6]
D[7]
D[8]
D[9]
D[10]
∞
∞
∞
∞
∞
∞
1,4
∞
∞
∞
1,4,7
∞
∞
1,4,7,2
∞
∞
1,4,7,2,3
∞
∞
1,4,7,2,3,9
∞
1,4,7,2,3,9,6
1,4,7,2,3,9,6,5
min(12+9;19)=19
13
min(D[i]) = 13, i = 10
Шаг 9.
На данном шаге алгоритма, кратчайшим из источника является путь в вершину 10: D[10] = 13. Вершину 10 включаем в S, предшествующей на минимальном пути для нее является вершина 9: Prev[10] = 9.
Рисунок 6.
Включение в S вершины 9 не ведет к перечету пути до единственной оставшейся вершины 8. Занесем данные в таблицу 8
Таблица 8.
S
D[2]
D[3]
D[4]
D[5]
D[6]
D[7]
D[8]
D[9]
D[10]
∞
∞
∞
∞
∞
∞
1,4
∞
∞
∞
1,4,7
∞
∞
1,4,7,2
∞
∞
1,4,7,2,3
∞
∞
1,4,7,2,3,9
∞
1,4,7,2,3,9,6
1,4,7,2,3,9,6,5
1,4,7,2,3,9,6,5,10
19
min(D[i]) = 19, i = 8
Шаг 10.
Данные таблицы 8 позволяют включить в S последнюю вершину графа – вершину 8. Длина кратчайшего пути для нее будет равна: D[8] = 19, вершиной предшествующей на кратчайшем пути до нее является вершина 6: Prev[8] = 6.
Рисунок 7.
Таким образом возможно сформулировать окончательные результаты работы алгоритма:
1. Кратчайшие пути от источника – вершины 1 до всех других вершин графа, а также значения вершин, предшествующих на этих путях, будут равны:
№ вершины
min(D[i]) =
Prev[i] =
2. Кратчайший путь пути от источника – вершины 1 до стока – вершины 10 будет равен: D[10] = 13 проходит через вершины: I →4→7→9→S
для вариантов №1-№15 приведены в таблице.
