каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город H?

Question

Реши задание на изображении

Расшифровка фото нейросетью:
[обрезано]
каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город H?
[Рисунок: ориентированный граф; вершины A (слева), C (сверху), B (снизу), D (в центре), E (сверху справа), F (снизу справа), G (справа), H (крайняя справа). Стрелки: A→C, A→D, A→B, C→E, C→D, B→D, B→F, D→E, D→F, D→G, E→G, F→G, G→H.]

Answer

Ответ: 11 различных путей — это число нужно ввести в поле.

Принцип решения. Пусть $N(X)$ — число путей из A в вершину $X$. Тогда

$$ N(X)=\sum N(Y) $$

по всем вершинам $Y$, из которых в $X$ идёт стрелка. Вершины обходим в таком порядке, чтобы все «входящие» в них уже были посчитаны.

По схеме:

$N(A)=1$;

в B и C ведёт только A: $N(B)=1$, $N(C)=1$;

в D ведут A, B, C: $N(D)=1+1+1=3$;

в E ведут C и D: $N(E)=1+3=4$;

в F ведут B и D: $N(F)=1+3=4$;

в G ведут D, E, F: $N(G)=3+4+4=11$;

в H ведёт только G: $N(H)=11$.

Проверка перебором. Я проверил все цепочки: A–B–D–E–G–H, A–B–D–F–G–H, A–B–D–G–H, A–B–F–G–H, A–C–D–E–G–H, A–C–D–F–G–H, A–C–D–G–H, A–C–E–G–H, A–D–E–G–H, A–D–F–G–H, A–D–G–H — ровно 11, сходится.

Главное для похожих задач: не перебирай всё вручную — иди по графу слева направо, складывая «накопленные» пути у каждой стрелки.