Dado um gráfico simples não direcionado como este:

Começando em D, A, B ou C (V_startEu tenho que calcular quantos caminhos possíveis existem desde o ponto de partida (V_start) para o ponto de partida (V_start) don etapas, onde cada aresta e vértice podem ser visitados um número ilimitado de vezes.

Eu estava pensando em fazer uma primeira busca profunda, parando quandosteps > n || (steps == n && vertex != V_start), no entanto, isso se torna bastante caro se, por exemplo,n = 1000000. Meu próximo pensamento me levou a combinar DFS com programação dinâmica, no entanto, é aí que estou preso.

(Isso não é lição de casa, apenas eu ficar preso brincando com gráficos e algoritmos por uma questão de aprendizado.)

Como eu iria resolver isso em um tempo razoável com um granden?