Путешествия с использованием графика

Question

Кто-нибудь может помочь мне лучше подумать, как адаптировать Алгоритм Дейкстры в этих условиях? Все, что я думал, было нехорошо.

Пример ввода:

GP4578 МАДРИД 1:00 PORTO 02:00

IK6587 PORTO 3:00 ВАЛЕНСИА 5:00 5:30 8:00 TENERIFE

AB5874 ВАЛЕНСИА 5:40 BERLIM 10:00

"VALENCIA 05:00 05:30" Это остановка, все они около 30 минут. Полет имеет время прилета и отправления, номер рейса, город происхождения и дестинации.

Итак, мне нужно получить кратчайший путь из города в другой, хорошо, никаких проблем. Я не могу структурировать это, меня судили с прошлой недели. Кто-то может дать мне идеалы? Кто моя вершина? Как использовать края?

Answer 1

Вот график я предлагаю: Два вида вершин:

1. вылета вершинных: аэропорт + вылета время
2. прибытия вершинных: аэропорт + прибытие время.

Два вида ребер:

1. полета край: от вылета вершины до прибытия вершины
2. ожидания края: от прилета вершины до вылета вершины позже в том же аэропорту.

Вес по краям - это продолжительность, проблема состоит из одного источника-кратчайшего пути, и вы можете решить его, используя алгоритм Диджстры, как вы упомянули. Что касается полетов с промежуточной посадкой, просто разделите их на секции.