4. Задания по теме «Динамическое программирование»

Транспортному предприятию требуется перевезти груз из пункта 1 в пункт 14. На рисунке показана сеть дорог и стоимость перевозки единицы груза между отдельными пунктами.

Определить маршрут доставки груза, которому соответствуют наименьшие затраты.

Значения коэффициентов условия задачи:

№ варианта значения	1	2	3	4	5	6	7	8	9	10
a1	20	18	22	15	17	19	23	16	21	24
a2	18	19	21	16	18	21	20	15	19	22
a3	19	17	20	17	16	20	22	17	20	23
a4	11	13	12	14	10	15	20	17	19	18
a5	15	14	11	10	12	13	16	15	16	17
a6	13	15	10	12	13	16	17	16	18	16
a7	12	16	9	11	9	14	19	14	15	19
a8	14	17	13	13	11	18	18	19	17	20
a9	12	18	14	16	15	17	15	18	14	21
a10	24	21	20	18	17	16	19	16	22	23
a11	21	19	20	21	22	18	23	17	18	19
a12	20	22	19	23	18	17	24	16	20	21
a13	22	21	18	22	21	19	20	18	19	18
a14	23	23	21	20	19	16	22	15	21	20
a15	24	18	17	24	20	15	21	19	22	22
a16	20	21	23	19	22	18	20	16	17	21
a17	22	17	19	23	18	17	19	22	20	21
a18	31	32	30	35	37	36	33	36	31	34
a19	32	33	29	31	36	37	34	35	32	33
a20	35	37	32	33	34	38	36	31	36	30
a21	37	36	31	34	36	35	40	37	39	38
a22	45	41	43	42	44	40	46	45	47	45
a23	28	32	30	25	26	28	33	31	29	27
a24	30	31	32	24	25	29	32	33	30	29