Чтобы решить задачу о количестве различных путей между двумя городами с помощью графа, можно использовать следующий алгоритм: 1

1. Определить смежные вершины и предков и потомков. 1 Две вершины, соединённые напрямую стрелкой, называются смежными, а вершина, из которой выходит стрелка, называется предком, а вершина, в которую входит стрелка, — потомком. 1
2. Каждой вершине, начиная с начальной, поставить в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. 1 Для начальной вершины (начала пути) индекс всегда равен 1. 1
3. Применить правило: индекс вершины равен сумме индексов её предков. 1 Подсчитывать индекс только тех вершин, индексы предков которых уже посчитаны. 1

Если подсчитываемые пути обязаны проходить через какой-либо город, то до начала подсчёта путей нужно исключить часть дорог. 2 Аналогично поступают с городами, в которых не нужно побывать: исключают из схемы все входящие и исходящие дороги избегаемого города. 2

Число путей конечно, если в графе нет циклов — замкнутых путей. 3