В мегаполисах даже хорошо знающие город водители пользуются навигаторами, потому что карты в нашем телефоне учитывают пробки, перекрытые улицы и, конечно, расстояние до нужного адреса. Навигационные приложения полезны не только автомобилистам - пешеходам они помогают найти подземные переходы, а “самокатчикам” не придется лишний раз в них спускаться.
Вы наверное уже догадались, что мы с вами поговорим о том, как навигаторы работают под капотом. Подумаем про данные - весь город, все улицы, переулки, ларьки и подъезды связаны. Нам надо оцифровать тот факт, что определённый дом находится на определенной улице, а эта улица, в свою очередь, связана с другими улицами и вообще на ней есть еще куча других построек. Давайте введем понятие вершины, вершиной мы назовем любое место в городе, куда нас сможет привести навигатор: улица, дом, подъезд и тд. Теперь давайте для каждой вершины сохраним вершины, с которыми она связана и через что они связаны. То есть если из дома 5 на улице А можно попасть в дом 4 на улице Я пройдя по улице Б, то мы этот факт сохраним. Пока не задумываясь о том, как именно мы уложим это все в памяти компьютера, мы получили какое множество вершин и информацию о том, как они друг с другом связаны. Это значит у нас есть модель города в виде графа.
Осталось научиться строить маршруты по городу. То есть у нас есть две вершины и мы должны понять какой путь самый оптимальный. Для простоты кратчайший маршрут будем считать оптимальным. Такую задачу отлично решает алгоритм Дейкстры, который мы можем запустить на нашем графе. Подробнее об этом алгоритме можно почитать тут.