Алгоритм нахождения путей в графе На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном…
Алгоритм нахождения путей в графе На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город З? Алгоритм: 1. В стартовой вершине можно оказаться только одним способом. Поэтому для неё количество путей равно 1. 2. Б = В = Г = Д = Е = А = 3. Ж = Б + В = 2 И = Д + Е = З = В + Г + Д + Ж + И = 4. В вершину К можно напрямую попасть из вершин Ж и И, но тогда мы не попадём в вершину З. Поэтому в вершину К мы можем попасть только из З, и тогда: К = З =
Разберем по шагам, заполняя недостающие значения по данному алгоритму.
Цель: посчитать число путей from А до К, проходящих через З.
- Текущая вершина А
- A = 1 (из стартовой вершины можно попасть одним способом).
- Б, В, Г, Д, Е
- Согласно алгоритму: Б = В = Г = Д = Е = А = 1.
- Ж (Жители)
- Ж = Б + В = 1 + 1 = 2.
- И
- И = Д + Е = 1 + 1 = 2.
- З
- З = В + Г + Д + Ж + И = 1 + 1 + 1 + 2 + 2 = 7.
- К
- Из условия: в вершину К можно попасть напрямую только из З, значит К = З = 7.
Вывод
- По пути А → … → З существует 7 различных путей, и каждый из них продолжается в К (благодаря единственному входу в К от З).
- Следовательно, количество путей из А в К, проходящих через З, равно 7.
