Kürzeste Reisezeit von der Quelle zum Ziel

Question

Betrachten Sie eine Liste von Stationen, sagen wir 10 Stationen, 'A' bis 'J', verbunden durch Züge zwischen ihnen.

In Bezug auf die grafische Darstellung, betrachten die Stationen (Vertices) und Züge zwischen ihnen (Kanten) Ausführen eines verbundenen Graphen zu bilden, aber nicht vollständig, dh jede Station von jeder Station erreichbar ist entweder direkt oder über anderer Stationen durch Hopfen. Am wichtigsten ist, dass diese Hops zwischen Ankunft und nächster Abfahrt warten. Verständlicherweise ist die Reisezeit zwischen zwei verbundenen Stationen unabhängig voneinander. Die Wartezeit bis zur nächsten Abfahrt hängt jedoch von Ihrer Ankunftsadresse ab.

HINWEIS: Ich erwähne Grafik nur zum besseren Verständnis. Man könnte darüber hinaus denken.

Problem: alle zwei Stationen gegeben und die Zeit von der Anfangsstation starten, wie kürzeste Zeit zum Ziel zu finden, in den Fällen des Hopfens, die Wartezeit zwischen Ankunft und Abreise zu zählen? Und welcher DS wird für dasselbe verwendet? Nehmen wir an, dass, wenn zwei Bahnhöfe durch einen Zug verbunden sind, nur ein Zug zwischen ihnen verkehrt.

Answer 1

IMHO Dijkstra sollte schließlich genug sein.

Wenn Sie Dijkstra von Knoten "A" ausführen, findet es den kürzesten Pfad zu allen anderen Knoten.

Auch wenn wir "Hops" haben, ist der schlimmste Fall, dass Sie früher zu einer Station kommen und dann müssen Sie auf denselben Zug warten, als ob Sie später mit einer anderen Route dorthin kommen würden.

Der einzige Unterschied ist, dass Sie Preis als „Zeit des Wartens + Fahrzeit“ statt nur „Zeit-Reise“

Dieses Verhalten zählen wird von Zügen verursacht, die echte „Ankunft/Abfahrt“.

Wenn jede Route für jeden A2-Knoten in jeder Knotenkombination A1 -> A2 -> A3 eine zufällige Strafe für den Übergang von A1 nach A3 über A2 erhält, wäre das unvorhersehbar, denke ich.