Алгоритм Дейкстры или как навигатор определяет оптимальный маршрут
Недавно датский математик решил задачу поиска кратчайшего пути при постоянно изменяющейся дорожной ситуации, над которой математики бились 40 лет.
Кристиан Вульф Нильсен создал алгоритм, который способен учитывать все изменения и обрабатывать поступающую информацию, затрачивая меньше времени и ресурсов. При этом этот метод применим к любым сетям или графам, в том числе и к интернету. Новый алгоритм работает с динамичным графом, который меняется с течением времени.
Так как подробности работы пока не публикуются, рассмотрим в ролике более простой вариант — Алгоритм Дейкстры. Это алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.
00:00 Задача кратчайшего пути
02:14 Алгоритм Дейкстры
06:07 Оптимизация алгоритма
