Скорее всего, вы использовали программу, работающую по алгоритму Дейкстры. Этот алгоритм используется во многих навигационных приложениях. Алгоритмы, как правило, кажутся сложными и полными технических деталей, но здесь мы просто будем придерживаться основ понимания того, что они делают, и общего представления о том, как они выполняют свою работу.

Алгоритм Дейкстры используется для поиска кратчайшего пути между двумя точками. Это то, что ваши навигационные приложения делают в бэкэнде. Алгоритм достигает этого, имея карту всех узлов (точек, мест и т. д.) для данной области, с которой вы работаете. Между каждым узлом находится число, представляющее стоимость перехода от одного узла к другому. Стоимость может быть представлением денежной стоимости; однако его также можно использовать для представления времени, расстояния или любого другого измеримого фактора. Когда мы начинаем, все переменные стоимости установлены на бесконечность. Когда мы тестируем каждый путь, мы обновляем его новыми, более низкими затратами.

Затем создаются два массива. Массивы в основном представляют собой списки элементов. Один массив для всех посещенных узлов. Другой — для всех непосещенных узлов.

Затем алгоритм повторяет серию шагов, пока не будет найден ответ.

  1. Посетите узел А
  2. Документируйте стоимость от A → A (0)
  3. Посетите всех непосещенных соседей A
  4. Если стоимость до этих узлов меньше текущей задокументированной стоимости, обновите расстояние
  5. По мере посещения каждого узла перемещайте его из непосещенного массива в посещенный массив.
  6. Повторите для всех узлов в непосещенном массиве.

Примечание: релаксация ребер v → w означает, что мы проверяем, является ли лучший путь из начального узла путешествием из s → v, v → w. Если эта стоимость меньше документально подтвержденной суммы, обновите ее.

Здесь мы можем увидеть узел, который непосредственно предшествует любому конкретному узлу на пути к этому узлу. Мы используем это, чтобы проследить наш обратный путь, чтобы получить путь с наименьшими затратами. Например, если мы пытаемся перейти от A → C, мы увидим, что E является предыдущим узлом для C. Что D является предыдущим узлом для E. Наконец, что A является предыдущим узлом для D. Наш путь с наименьшей стоимостью затем А → D → E → C.