Digamos que tenemos dos gráficos dirigidos y de ponderación positiva en un conjunto de vértices (el primer gráfico representa, por ejemplo, vías de ferrocarril y el segundo, líneas de autobuses; los vértices son paradas de autobús o estaciones de vías de ferrocarril o ambas). Necesitamos encontrar la ruta más corta de A a B, pero no podemos cambiar el tipo de transporte más de N veces.

Intenté modificar el algoritmo de Dijkstra, pero funciona solo en unos pocos gráficos "no tan malos y complicados" y creo que necesito probar algo diferente.

¿Cómo representar mejor ese "gráfico de dos" y cómo administrar la cantidad limitada de cambios en el desplazamiento del gráfico? ¿Existe la posibilidad de adaptar el algoritmo de Dijkstra en este caso? Cualquier idea y pistas serán útiles.

Editar: Bueno, olvidé una cosa (creo que es bastante importante): N = 0,1,2, ...; podemos crear cualquier representación gráfica que nos guste y, por supuesto, pueden existir un máximo de 4 bordes entre cada dos nodos (1 carril de autobuses y 1 ferrocarril en una dirección, y 1 carril de autobuses y 1 ferrocarril en la segunda dirección).