Часть 1. Как навигационные приложения прокладывают кратчайший путь?

Кто-нибудь задумывался, каким образом современные навигационные приложения по типу 2GIS, Google Maps или же Яндекс.Карты прокладывают маршруты из точки A в точку B? При этом такие приложения пытаются выбрать для вас наиболее кратчайший маршрут. В этой статье я расскажу основные алгоритмы, на которых базируются все эти приложения при построении каких либо маршрутов. И так, начнем. 

В большинстве своем навигационные системы для построения маршрутов используют такую структуру данных, как “граф”. Коротко говоря, Граф - это структура данных, описывающая отношения между объектами с помощью узлов и ребер. Узел может быть напрямую соединен с несколькими другими узлами. Эти узлы называются соседями. Существуют два вида графа. Это направленный и ненаправленный. 

В направленном графе отношения действуют только в одну сторону. В данном примере узел B является соседом А, но узел А не является соседом для узла B. В ненаправленном графе стрелок нет, и каждый из узлов является соседом по отношению друг к другу. В принципе, это все, что нужно знать о графах. 

И так, давайте продолжим. Предположим, что у нас есть два узла: A и B, пусть это будет наш Дом и Работа, соответственно. Допустим, вы находитесь Дома и хотите добраться до Работы. Вы намереваетесь доехать на автобусе с минимальным количеством пересадок. Давайте попробуем визуализировать полученную информацию в виде графа. Возможны следующие варианты: 

Задача такого типа является задачей кратчайшего пути. Часто требуется найти некий кратчайший путь: путь к дому вашего друга, путь к победе в шахматной партии (за наименьшее количество ходов) и т.д. Алгоритм для решения задачи поиска кратчайшего пути называется - поиском в ширину. 

В нашем случае кратчайший путь определяется наименьшим количеством пересадок. Возможно ли добраться до узла B без пересадок? Увы, нет. Без пересадок мы доберемся только до узлов C и D. 

А с одной пересадкой? Да, маршрут с одной пересадкой выглядит следующим образом: 

Будем считать, что узлы до которых можно добраться за 1 ход - это связи первого уровня, узлы до которых можно добраться за 2 хода - связи второго уровня и т.д. 

Связи первого уровня предпочтительнее связей второго уровня, связи второго уровня предпочтительнее связей третьего уровня и т.д. Отсюда следует, что поиск по узлам второго уровня не должен производиться, пока мы не обойдем все узлы первого уровня и не убедимся, что за 1 ход невозможно добраться до конечной точки B. 

Также это можно объяснить тем, что связи первого уровня добавляются в поиск раньше связей второго уровня. Для реализации этого подхода отлично подходят Очереди. Очередь относится к категории структур данных FIFO (First In, First Out). 

Заметьте, что узел B является одновременно узлом второго уровня и узлом третьего уровня. Это происходит из-за того, что до него можно добраться за различное количество ходов. 

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

const graph = { 

A: ['C', 'D'], 

B: [], 

C: ['B'], 

D: ['E'],

E: ['B'], 

} 

После этого нам необходимо создать очередь. Так как в JS нет специального объекта, предназначенного для создания очередей, как это, например, реализовано в Python или Java, я буду использовать обычный массив и его методы. Ну и теперь мы можем реализовать сам алгоритм:

const node_is_endpoint = (node) => { 

    if (node === 'B') { <------ there can be any check here 

        return true 

    } 

    return false 

} 

const search = (graph, startNode) => { 

    const search_queue = [] <------ create a queue 

    search_queue.unshift(...graph[startNode]) <------ add the start node to the queue

    const searched = [] <------- checked nodes do not need to be checked again.

    while (search_queue.length) { 

        const node = search_queue.shift() <------- remove the first node from the queue

        if (!searched.includes(node)) { 

            if (node_is_endpoint(node)) { <------- check if this is endpoint 

                console.log(`We are on place!`) 

                return true 

            } else { 

                search_queue.push(...graph[node]) <------- add all neighbors of this node            

                searched.push(node) 

            } 

        } 

    } 

    return false 

} 

Вот и все, мы реализовали алгоритм поиска в ширину. 

P.S. Но что, если наш граф будет выглядеть вот так? 

Ох, а точно ли этот путь является кратчайшим? И никакой поиск в ширину нам тут уже не поможет. На помощь решения такой задачи существует алгоритм Дейкстры. Но разберем мы его в следующей части.