В заданном ациклическом ориентированном графе с весами G. Бесплатный доступ к контрольной работе

Реферат.Справочник
Контрольные работы по высшей математике
В заданном ациклическом ориентированном графе с весами G

В заданном ациклическом ориентированном графе с весами G .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

В заданном ациклическом ориентированном графе с весами G (V, E), где V {1, ..., n} - множество вершин графа и E - множество дуг (ki, kj, wij) с весами wij , найти маршрут минимальной длины, соединяющий начальную и конечную вершины. n12, E {(1,2,2), (1,3,3), (2,4,5), (2,5,7), (3,5,4), (3,6,2), (4,9,1), (4,7,4), (4,8,2), (5,7,3), (5,8,2), (6,7,1), (6,8,3), (6,9,2), (7,10,2), (8,10,3), (8,11,9), (9,10,5), (9,11,4), (10,12,9), (11,12,8)}

Решение

Потяни, чтобы посмотреть

В соответствии с методом динамического программирования выполним обратный и прямой ход. Обратный ход. Находим функции G4, G3, G2, G1, G0:
G410=f510,12=9
G411=f511,12=8
G37=G410+f47,10=9+2=11
G38=minG410+f48,10;G411+f48,11=min9+3;8+9=17
G39=minG410+f49,10;G411+f49,11=min9+5;8+4=12
G24=minG37+f34,7;G38+f34,8;G39+f34,9=min11+4;17+2;12+1=13
G25=minG37+f35,7;G38+f35,8=min11+3;17+2=14
G26=minG37+f36,7;G38+f36,8;G39+f36,9=min11+1;17+3;12+2=12
G12=minG24+f22,4;G25+f22,5=min13+5;14+7=18
G13=minG25+f23,5;G26+f23,6=min14+4;12+2=14
G01=minG12+f11,2;G13+f11,3=min18+2;14+3=17
Прямой ход

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу