Мне дается файл с 600000 дорогами, которые связаны с перекрестками. Я должен сделать программу, которая найдет кратчайший путь между двумя соединениями. Но также необходимо найти самый быстрый путь между двумя другими узлами. Я думал об использовании BFS-алгоритма для решения этой проблемы, но я не знаю, правильно ли это сделать. Я также нашел несколько других links, которые используют алгоритм Дейкстры для решения этой проблемы.Найти самый короткий путь или самый быстрый путь
Я не ищу полный код mashup, но я просто хочу знать, буду ли я двигаться в правильном направлении.
PS: Входные файлы выглядят следующим образом:
4370 6701 3079 2019 60
32840 9113 17817 7483 30
40758 13107 3445 2505 30
3074 11089 19209 2960 40
...
В следующем формате: Roadnumber - Начало перехода - End узел - Расстояние (в метрах) - Ограничение скорости (в км/ч)
EDIT (для справок в будущем): Я решил использовать алгоритм Дейкстры для решения этой проблемы, и это сработало как шарм. Большое вам спасибо! Оказывается, требуется всего несколько секунд, чтобы найти кратчайший путь между двумя узлами на графике из более чем 600 000 узлов.
Я думаю, что вы направляетесь в правильном направлении. –
Да, алгоритм Дейкстры - это путь. Для кратчайшего пути используйте расстояние между двумя переходами, а для наиболее быстрого использования - время, необходимое для перемещения между двумя переходами. – amit
Спасибо. Так было бы хорошей идеей сохранить соединения в хэш-карте, которая связывает соединение с подключенной дорогой? –