Поиск соединений в 3 векторах строки

Question

Я написал на C++ код, который находит кратчайший путь между двумя городами, связанными дорогами или рейсами. Города могут быть связаны с прямыми рейсами или косвенными. Пользователь может ввести рейсы, как это:

AAA AAG 300 
AAA AAB 1 
AAA AAG 298 
AAB AAC 1 
AAB AAG 297 
AAC AAD 1 
AAC AAG 296 
AAD AAE 1 
AAD AAG 295 
AAE AAF 1 
AAE AAG 294 
AAF AAG 1 

Где первая строка покидает город, второй является местом, а число время полета. хранить эти значения в 3-х векторах:

vector<string> leavingCities; 
    vector<string> destCities; 
    vector<int> flightTimes; 

У меня есть проблемы с поиска непрямых рейсов в этих векторах - я имею в виду, иногда прямое время полета от ААА до AAG намного больше, чем непрямой рейс через АИТ, AAC, AAD, AAE и AAF, а затем я должен выбрать более короткий маршрут и хранить города, в которые я путешествовал. Есть ли какое-либо решение для поиска кратчайшего времени и маршрута? Список рейсов может варьироваться и не должен выглядеть так. Может быть, есть лучший контейнер для хранения данных? Пожалуйста, помогите мне.

Answer 1

Используйте Dijkstra's algorithm, чтобы найти кратчайший маршрут.

Answer 2

Вы действительно должны разделить свой вопрос на понимание как вы собираетесь его решить, а затем войти в код. Если вы не понимаете, как вы его решаете, обычно просто писать код не поможет.

Во-первых, ваша проблема может быть классифицирована как поиск самого короткого пути в алгоритме Graph. В Википедии есть целая страница, но алгоритм Dijkstra's, вероятно, лучший для вас.

Как только вы поняли, как это сделать, вы можете реализовать его. Если вы можете их использовать, есть много хороших графических библиотек, таких как Boost.Graph, но я подозреваю, что в качестве задания вам будет предложено реализовать его самостоятельно с нуля. Тем не менее, я бы не рекомендовал смотреть источники Boost как неопытного программиста - они довольно страшные, хотя и отличный способ узнать, как только у вас будет немного больше опыта под вашим поясом.

Успехов