Алгоритм Дейкстры или как навигатор определяет оптимальный маршрут

Всем привет! С вами Георгий Вольфсон. Это реальная математика на канале QWERTY. Надеюсь, что вы давно уже на нас подписаны, но те из вас, кто еще нет, срочно делайте это!

Многие из вас, я думаю, уже слышали новость о том, что датский математик Кристиан Вульф Нельсон решил-таки проблему поиска кратчайшего пути в графе. Этой самой проблеме уже более 40 лет. В комментариях можно прочитать недовольство по поводу этой новости, что, в смысле, решил проблему, уже давно решено, алгоритмы существуют. Не очень понятно, что же он тогда сделал.

Вот сегодня мы в этом и разберемся. А о какой же проблеме идет речь?

Представим себе, что у нас есть граф. А что такое граф? Это значит, что есть какие-то вершины, эти вершины как-то соединены ребрами. Какие-то вершины могут быть соединены, какие-то нет. Можете для простоты представлять себе, что вершина — это некий перекресток, ну а между перекрестками протянуты улицы, которые соединяют эти перекрестки. Или, если вам так проще, города, которые соединены авиалиниями. Все это примеры графов.

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

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

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

Давно, еще более 40 лет назад, были придуманы разные алгоритмы. Наиболее популярны, наверное, это алгоритм Дейкстры, появившийся в середине прошлого века. Потом его усовершенствовали, появился алгоритм A-Star, или иногда называют «A звезда», со звездочкой. Более жаргоном они так или иначе называются.

Вот про алгоритм Dijkstra сейчас и поговорю. Ну давайте разберемся на конкретном примере. Вот пусть у нас есть A, B, C, D и E — это вершины нашего графа, ну или перекрестки.