Имеется простой неориентированный граф, подобный этому:

Начиная с D, A, B или C (V_start) & # x2014; Я должен рассчитать, сколько возможных путей существует от начальной точки (V_start) к начальной точке (V_start) изn шаги, где каждое ребро и вершину можно посещать неограниченное количество раз.

Я думал о том, чтобы сделать первый глубокий поиск, останавливаясь, когдаsteps > n || (steps == n && vertex != V_start)Однако это становится довольно дорого, если, например,n = 1000000, Моя следующая мысль привела меня к объединению DFS с динамическим программированием, однако именно здесь я застрял.

(Это не домашнее задание, просто я застреваю, играя с графиками и алгоритмами ради обучения.)

Как бы я решил это в разумные сроки с большимn?