а)
u | 0 | 1 | 2 | 3 | 4 | 6 | 5 | 7 | 8 |
T | 1,2 | 2,3,4,6 | 3,4,6,5 | 4,6,5,7 | 6,5,7,8 | 5,7,8 | 7,8 | 8 | Æ |
б)
u | 0 | 2 | 6 | 8 | 7 | 4 | 5 | 3 | 1 |
T | 1,2 | 1,3,5,6 | 1,3,5,4,7,8 | 1,3,5,4,7 | 1,3,5,4 | 1,3,5 | 1,3 | 1 | Æ |
12.0. Для графа, построенного в задаче 10, найти минимальную по суммарному времени сеть дорог, соединяющую все пункты (кратчайший остов), используя алгоритм Краскала.
Решение. Упорядочим ребра графа по неубыванию длин:
2,3 | 2,5 | 7,8 | 7,6 | 5,7 | 1,3 | 4,6 | 4,8 | 0,1 | 0,2 | 1,6 | 6,8 | 3,7 | 1,4 | 2,6 |
4 | 6 | 7 | 8 | 8 | 8 | 9 | 10 | 10 | 11 | 12 | 13 | 13 | 13 | 18 |
Идея алгоритма Краскала состоит в том, чтобы формировать дерево K(V,E), выбирая ребра с наименьшим весом так, чтобы не возникал цикл. Строим граф кратчайшего остова K. Он имеет множество вершин V = {
, 
, …, 
}. Изначально множество ребер E пусто.
Пока таблица не пуста, первое в списке ребро (u, v) включаем в E, удаляем из таблицы его и все ребра, добавление которых приводит к циклу в K.
1) 
.
2,5 | 7,8 | 7,6 | 5,7 | 1,3 | 4,6 | 4,8 | 0,1 | 0,2 | 1,6 | 6,8 | 3,7 | 1,4 | 2,6 |
6 | 7 | 8 | 8 | 8 | 9 | 10 | 10 | 11 | 12 | 13 | 13 | 13 | 18 |
2) 
.
7,8 | 7,6 | 5,7 | 1,3 | 4,6 | 4,8 | 0,1 | 0,2 | 1,6 | 6,8 | 3,7 | 1,4 | 2,6 |
7 | 8 | 8 | 8 | 9 | 10 | 10 | 11 | 12 | 13 | 13 | 13 | 18 |
3) 
.
7,6 | 5,7 | 1,3 | 4,6 | 4,8 | 0,1 | 0,2 | 1,6 | 6,8 | 3,7 | 1,4 | 2,6 |
8 | 8 | 8 | 9 | 10 | 10 | 11 | 12 | 13 | 13 | 13 | 18 |
4) 
.
5,7 | 1,3 | 4,6 | 4,8 | 0,1 | 0,2 | 1,6 | 3,7 | 1,4 | 2,6 |
8 | 8 | 9 | 10 | 10 | 11 | 12 | 13 | 13 | 18 |
5) 
.
1,3 | 4,6 | 4,8 | 0,1 | 0,2 | 1,6 | 1,4 |
8 | 9 | 10 | 10 | 11 | 12 | 13 |
6) 
.
4,6 | 4,8 | 0,1 | 0,2 | 1,4 |
9 | 10 | 10 | 11 | 13 |
7) 
.
0,1 | 0,2 |
10 | 11 |
8) 
.
Таблица пуста.
Ответ: сумма длин дорог минимальной сети равна 60.
13.0 Для графа, построенного в задаче 10, найти самый короткий (по времени) путь из пункта 1 в каждый пункт (использовать алгоритм Дейкстра).
Решение. Найдем кратчайший путь из вершины x0 в каждую вершину, пользуясь алгоритмом Декстра. Будем отмечать все этапы алгоритма на рисунке 3.
Рис. 3.
Начальный шаг. Вершине x0 присваивается постоянная метка (0, x¥), остальным вершинам – временные метки (¥, x¥ ), которые не записываем. Вершины с постоянными метками будем помечать знаком “´”.
Общий шаг.
1. Начнем с единственной вершины x0, имеющей постоянную метку. Из неё выходят дуги в вершины x1 и x2. Вычислим для них ярлыки: l¢1=0+10=10, l¢2=0+11=11. Так как l¢1, l¢2 < ¥, то присваиваем новые временные метки: вершине x1 – метку (10, x0), а вершине x2 – метку (11, x0).
Из всех временных наименьший ярлык имеет метка вершины x1. Делаем ее постоянной и повторяем общий шаг для вершины x1.
2. Из вершины x1 выходят дуги в вершины x3, x4, x6. Вычислим для них ярлыки: l¢3=10+18=18, l¢4=10+13=23, l¢6=10+12=22. Так как все они меньше существующих ярлыков, то присваиваем новые временные метки: вершине x3 – метку (18, x1), вершине x4 – метку (23, x1), вершине x6 – метку (22, x1).
Из всех временных наименьший ярлык имеет метка вершины x2. Делаем ее постоянной и повторяем общий шаг для вершины x2.
3. Из вершины x2 выходят дуги в вершины x3, x5, x6. Вычислим для них ярлыки: l¢3=11+4=15, l¢5=11+6=17, l¢6=11+18=29. Так как l¢3=15<18, а l¢5=17<¥, то присваиваем новые временные метки: вершине x3 – метку (15, x2), вершине x5 – метку (17, x2). Метка вершины x6 остается без изменений – (22, x1).
Из всех временных наименьший ярлык имеет метка вершины x3. Делаем ее постоянной и повторяем общий шаг для вершины x3.
4. Из вершины x3 выходит дуга в вершину x7. Вычислим для неё ярлык: l¢7=15+13=28. Так как l¢7<¥, то присваиваем вершине x7 новую временную метку (28, x3).
Из всех временных наименьший ярлык имеет метка вершины x5. Делаем ее постоянной и повторяем общий шаг для вершины x5.
5. Из вершины x5 выходит дуга в вершину x7. Вычислим для неё ярлык: l¢7=17+8=25. Так как l¢7=25<28, то присваиваем вершине x7 новую временную метку (25, x5).
Из всех временных наименьший ярлык имеет метка вершины x6. Делаем ее постоянной и повторяем общий шаг для вершины x6.
6. Из вершины x6 выходит дуга в вершину x8. Вычислим для неё ярлык: l¢8=22+13=35. Так как l¢8<¥, то присваиваем вершине x8 новую временную метку (35, x6).
Из всех временных наименьший ярлык имеет метка вершины x4. Делаем ее постоянной и повторяем общий шаг для вершины x4.
7. Из вершины x4 выходят дуги в вершины x6 и x8. Но вершина x6 уже имеет постоянную метку, поэтому ее не рассматриваем. Вычислим ярлык для x8: l¢8 = 23+10=33. Так как l¢8=33<35, то присваиваем вершине x8 новую временную метку (33, x4).
Из всех временных наименьший ярлык имеет метка вершины x7. Делаем ее постоянной и повторяем общий шаг для вершины x7.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 |
