Kann ich den kürzesten Pfad von Dijkstra verwenden?

Question

Ich habe eine Textdatei mit einer Liste von Flughafen-Codes und Zeiten zwischen den einzelnen wie folgt formatiert:

AER, KZN, 1,8835

Wo dies für die erste Flughafen steht, der zweite Flughafen, die Zeit in Stunden zwischen ihnen (nicht bidirektional).

Ich nehme an, es gibt eine 2-stündige Verspätung bei jedem Zwischenstopp und versuchen herauszufinden, wie viele Flughäfen von Boston (BOS) innerhalb von 10 Stunden erreichbar sind. Ich weiß, wenn ich alle Knoten in Dijkstra platziere, kann ich kürzeste Wege zwischen jedem Knoten finden, aber kann ich ihn auch benutzen, um dieses Problem zu lösen?

Answer 1

Ja, Sie können: Dijkstra unter BOS starten und stoppen (früher Abbruch), wenn der nächste Flughafen einen längeren Weg als die 10 Stunden erreicht hat.