Eu já resolvi a maioria das perguntas postadasaqui, exceto o caminho mais longo. Eu li o artigo da Wikipedia sobre caminhos mais longos e parece ser um problema fácil se o gráfico for acíclico, o que não é o meu.

Como resolvo o problema então? Força bruta, verificando todos os caminhos possíveis? Como eu começo a fazer isso?

Eu sei que vai demorar muito em um gráfico com ~ 18000. Mas eu só quero desenvolvê-lo de qualquer maneira, porque é necessário para o projeto e vou testá-lo e mostrá-lo ao instrutor em um gráfico de menor escala, onde o tempo de execução é de apenas um ou dois segundos.

Pelo menos eu fiz todas as tarefas necessárias e tenho uma prova de conceito de que funciona, mas não há melhor maneira em gráficos cíclicos. Mas não sei por onde começar a verificar todos esses caminhos ...