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

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

Задача. На рисунке  - схема дорог, связывающих города А, B, C, D, E, G, H, F. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город D?

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

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

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

   2.1.индекс В равен 1 (предок у В один – вершина A)
   2.2.индекс G равен 1 (предок у G один – вершина A).
   2.3.индекс Е равен 1+1+1=3 (предки вершины Е - А, В и G).
   2.4.индекс С равен 1+3=4 (предки вершины С - В и Е).
   2.5.индекс Н равен 3+1=4 (предки вершины Н – Е и G).
   2.6.индекс F равен 3+4=7 (предки вершины F – Е и Н).
   2.7.индекс вершины D равен 4+3+7=14 (предки вершины D – C, Е и F).

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

4. Ответ: 14.

Решите самостоятельно:

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

а) б)