Powiedzmy, że mamy dwa ukierunkowane i dodatnio ważone wykresy na jednym zestawie wierzchołków (pierwszy wykres przedstawia na przykład drogi kolejowe, a drugi - pasy autobusowe; wierzchołki to przystanki autobusowe lub dworce kolejowe lub oba). Musimy znaleźć najkrótszą drogę od A do B, ale nie możemy zmienić rodzaju transportu więcej niż N razy.

Próbowałem zmodyfikować algorytm Dijkstry, ale działa on tylko na kilku „nie tak średnich i skomplikowanych” wykresach i myślę, że muszę spróbować czegoś innego.

Jak najlepiej przedstawić ten „dwa wykresy” i jak zarządzać ograniczoną ilością zmian w przechodzeniu przez wykres? Czy istnieje możliwość dostosowania algorytmu Dijkstry do tego? Wszelkie pomysły i wskazówki będą pomocne.

Edytować: Cóż, zapomniałem o jednej rzeczy (myślę, że to bardzo ważne): N = 0,1,2, ...; możemy wymyślić dowolną reprezentację graficzną, którą lubimy i oczywiście mogą istnieć maksymalnie 4 krawędzie pomiędzy dwoma węzłami (1 pas autobusowy i 1 linia kolejowa w jednym kierunku, 1 pas autobusowy i 1 linia kolejowa w drugim kierunku).