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

Опубликовано 1 апреля 2021, 8:34

Недавно датский математик решил задачу поиска кратчайшего пути при постоянно изменяющейся дорожной ситуации, над которой математики бились 40 лет.

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

Так как подробности работы пока не публикуются, рассмотрим в ролике более простой вариант — Алгоритм Дейкстры. Это алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.

00:00 Задача кратчайшего пути
02:14 Алгоритм Дейкстры
06:07 Оптимизация алгоритма

#РеальнаяМатематика #навигатор #математикаграф #математика #qwerty