Алгоритм по решению задач на поиск количества различных путей в графе, не проходящих через город N

Алгоритм по решению задач на поиск количества различных путей в графе,

не проходящих через город N.

Задача. На рисунке  - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, не проходящих через пункт В?

Граф ориентированный. Две вершины, соединенные напрямую стрелкой, называются смежными. Вершина, из которой выходит стрелка, называется предком, а вершина, в которую входит стрелка – потомком. Количество путей, которыми можно попасть в некоторую вершину, равно сумме количеств путей предков этой вершины.

1. Убираем из рассмотрения те пути, которые входят в пункт В и выходят из пункта В.

На рисунке вычёркиваем пути из Б в В, из А в В, из В в Д, из В в Е, из В в Г.

1. Каждой вершине, начиная с начальной (А) ставим с соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1.

2. Применяем правило «индекс вершины равен сумме индексов его предков». Подсчитываем индекс только тех вершин, индексы предков которых уже посчитаны.

   3.1.индекс Б равен 1 (предок у Б один – вершина A)
   3.2.индекс Г равен 1 (предок вершины Г – вершина A).
   3.3.индекс Д равен1 (предок у вершины Д один – вершина Б).
   3.4.индекс Е равен 1+1=2 (предки у вершины Е - вершины Д и Г).
   3.5.индекс И равен 2+1=3 (предки у вершины И – вершины Е и Г).
   3.6.индекс Ж равен 1 (предок у вершины Ж один – вершина Д).
   3.7.индекс вершины К равен 1+1+3=5 (предки вершины К – вершины Д, Ж и З).

3. Индекс вершины К – ответ задачи.

4. Ответ: 5.