Digamos que tenhamos dois gráficos direcionados e de peso positivo em um conjunto de vértices (o primeiro gráfico representa, por exemplo, ferrovias e o segundo - faixas de ônibus; vértices são pontos de ônibus ou estações de trem ou ambas). Precisamos encontrar o caminho mais curto de A a B, mas não podemos alterar o tipo de transporte mais de N vezes.

Eu estava tentando modificar o algoritmo do Dijkstra, mas ele está funcionando apenas em alguns gráficos "não tão ruins e complicados" e acho que preciso tentar algo diferente.

Como melhor representar esse "dois gráficos" e como gerenciar a quantidade limitada de alterações ao percorrer o gráfico? Existe a possibilidade de adaptar o algoritmo de Dijkstra neste? Todas as idéias e pistas serão úteis.

Editar: Bem, eu esqueci uma coisa (acho que é muito importante): N = 0,1,2, ...; podemos criar qualquer representação gráfica de que gostamos e, é claro, podem existir no máximo 4 arestas entre cada dois nós (1 faixa de ônibus e 1 ferrovia em uma direção e 1 faixa de ônibus e 1 ferrovia na segunda direção).