Начнем считать количество путей с конца маршрута – с города М. NX  — количество различных путей из города А в город X, N  — общее число путей.

В "М" можно приехать из G, H, F, K или L, поэтому N = NМ = NG + NH + NF + N К + N L (1)

Аналогично:

NG = NB;
NH = NB + NC + NF;
NF = NC + NА + ND;
NК = NF + ND;
NL = NE + ND.

Добавим еще вершины:

NB = NA + NC;
NC = NA = 1;
ND = NA= 1;
NE = NА + ND = 2.

Преобразуем вершины:

NB = NA + NC = 2;
NC = NA = 1;
ND = NA= 1;
NE = NА + ND = 2.

NG = NB = 2;
NH = NB + NC + NF= 2 + 1 + 3 = 6;
NF = NC + NА + ND = 1 + 1 + 1 = 3;
NК = NF + ND = 3 + 1 = 4;
NL = NE + ND = 2 + 1 = 3.

Подставим в формулу (1):

N = NМ = 2 + 6 + 3 + 4 + 3 = 18.