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

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