На рисунке — схема дорог, связывающих города А, Б, В, Г,Д, Е, Ж, 3, и, к, л, Ми Н. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Н?
Привет! Давай вместе разберёмся с этой задачей.
Нужно определить количество различных путей из города А в город Н. Это задача на графы, где города — это вершины, а дороги — рёбра с направлением.
Начнём с города А и будем записывать количество путей до каждой из вершин, двигаясь по стрелкам.
Из города А в Б идёт один путь, следовательно, до Б — 1 путь.
Из города А также есть путь сразу в Г, поэтому у Г — 1 путь (А → Г).
Дальше строим:
- Из Б в В — 1 путь (А → Б).
- Из В в Е и в Ж — по 1 пути (А → Б → В).
- Из Г в Д — 1 путь (А → Г).
- Из Д в Е — 1 путь, добавляем его к имеющимся путям до Е (А → Г → Д).
Продолжаем:
- До Ж добавляются все пути, которые ведут в Ж через В (А → Б → В → Ж) и через Е (А → Б → В → Е → Ж и А → Г → Д → Е → Ж).
- До И идут все пути через Ж (аналогично считать).
Далее смотрим, как добраться до Н:
- Считаем все пути, которые приходят в И и идут в Н.
- Аналогично считаем все, кто идёт через другие промежуточные города как ЖИ и К.
Находим суммарное количество в Н.
Таким образом, вышеописанным способом прибавляем количество путей к каждой вершине. Это техника динамического программирования на графе.
Если кратко: для каждой вершины мы суммируем пути из всех предыдущих, откуда здесь можно было попасть.
Попробуй нарисовать и посчитать каждый шаг для закрепления!
