Решение задачи: количество путей в графе от А до К

Для решения этой задачи воспользуемся методом динамического программирования, последовательно подсчитывая количество путей в каждый город. Количество путей в пункт назначения равно сумме путей во все пункты, из которых в него ведут стрелки. Решение: 1. Примем количество путей в начальный город А за единицу: \( N_A = 1 \) 2. Город Б: в него ведет только одна дорога из А. \( N_Б = N_A = 1 \) 3. Город Д: в него ведет только одна дорога из А. \( N_Д = N_A = 1 \) 4. Город Г: в него ведут дороги из А и Д. \( N_Г = N_A + N_Д = 1 + 1 = 2 \) 5. Город В: в него ведут дороги из А, Б и Г. \( N_В = N_A + N_Б + N_Г = 1 + 1 + 2 = 4 \) 6. Город Е: в него ведут дороги из Б и В. \( N_Е = N_Б + N_В = 1 + 4 = 5 \) 7. Город Ж: в него ведут дороги из Г и Д. \( N_Ж = N_Г + N_Д = 2 + 1 = 3 \) 8. Город К: в него ведут дороги из Е, В, Г и Ж. \( N_К = N_Е + N_В + N_Г + N_Ж \) \( N_К = 5 + 4 + 2 + 3 = 14 \) Ответ: 14.