Задача с дорогами.

Можно "выкусывать" города.
Введем понятие кратности дороги, обозначим Кр (АБ) - это количество дорог из города А в город Б.
На начальном этапе в вашем графе кратность всех дорог = 1.

На каждом шаге будем удалять с карты по одному городу, пока не останется два - начальный и конечный.
Между ними будет одна дорога, кратность которой будет равна числу путей.

Например удалим В. Для неё есть входящие из А и Б кратности оба 1 и исходящий в Е кратности 1.
Если бы исходящих не было, то мы могли бы удалить тупиковый город и дороги, которые в него входят.
В двойном цикле по каждой входящей и исходящей (для примера входящая АВ, исходящая ВЕ)
-- добавляем дорогу АВ на дорогу АЕ кратности Кр (АВ) *Кр (ВЕ) =1*1=1, так как АЕ уже есть, то добавим кратность к ней, теперь Кр (АЕ) =1+1=2
После того как цикл выполнится 2*1=2 раза удалим город В и дороги АВ, БВ и БЕ. И мы стали на 1 шаг ближе к концу алгоритма, так как сократили количество городов.

ВНИМАНИЕ: если бы на этом шаге оказалось, что надо добавить дорогу АА, то нам бы не повезло (или повезло, так как всё просто) - граф содержит циклы и путей либо бесконечно много, либо нет совсем. Ибо по такому циклу мы могли бы крутиться до бесконечности как по КАДу.

Почему выбран город В? А потому, что у него есть дорога, входящая из начального города (А). Так мы перебираем все исходящие города для начального города, пока не останется только один конечный город. Конечный город может появиться в этом списке в процессе "вырезания", а может получиться так, что исходящие дороги закончились, а конечного города среди них нет (логично, ибо их нет вообще), в последнем случае путей из начального города в конечный нет.

Для понимания можно сделать карандашиком и ластиком на бумаге, надписывая кратность дуги между вершинами и подправляя граф, стирая вершины и дуги на каждом шаге. Только возьмите граф попроще или посчитайте пути из Н в Ф или из К в Ф

ЗЫ
Предложенный алгоритм заточен под представление графа в виде МАТРИЦЫ или СПИСКА СМЕЖНОСТИ

ЗЗЫ
Дополнительный вариант для проверки (другой алгоритм): Нахождение количества путей в графе

Самый тупой алгоритм: ставишь на число 1 (из него начинаем единственным путем).
А дальше на всех узлах, куда ведут пути только из пронумерованных, ставим суммы исходных узлов:
- на всех узлах, куда ведет только путь из А, ставим тоже 1 (Б и Д - туда можно добраться только из А).
- на всех узлах, куда ведут пути только из А, Б, Д, ставим суммы ( В = А+Б = 2, Г = А + Д = 2).
- на Е ставим А+Б+В+Г+Д = 1 + 1 + 2 + 2 + 1 = 7
и т. д., пока не доберемся до Ф.

Называется: "обход ориентированного графа", гугель в помощь, до фига алгоритмов.

еще проще есть.
просто рисовать дерево и смотрим на каждом шаге,
если есть повторяющиеся нити - вписываем их уже готовыми.
всего 40 нитей