Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-21

1 <a>#статьи</a>

2 <ul><li>20 ноя 2023</li>

3 <li>0</li>

4 </ul><h2>Алгоритм Дейкстры: что это такое, как работает и где используется</h2>

5 С его помощью строят маршруты навигаторы, роботы и персонажи компьютерных игр.

6 Иллюстрация: Оля Ежак для Skillbox Media

7 Программист, консультант, специалист по документированию. Легко и доступно рассказывает о сложных вещах в программировании и дизайне.

8 Все мы пользуемся приложениями-навигаторами - вводим начальную и конечную точки, а программа строит самый оптимальный, на её взгляд, маршрут. Для этого она использует так называемые алгоритмы поиска кратчайшего пути. Сегодня поговорим о самых популярных из них - алгоритмах Дейкстры и А*. Выясним, как они работают, где применяются и чем отличаются друг от друга.

9 Алгоритм Дейкстры - это метод нахождения кратчайших путей от одной вершины графа ко всем остальным.

10 Граф - это математическая структура, которая состоит из вершин (узлов) и рёбер (связей) между ними. Рёбра могут иметь направление, а также веса - числа, которые обозначают силу связей с вершинами.

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

12 Инфографика: Майя Мальгина для Skillbox MediaНо, конечно, одними социальными сетями прикладной смысл графов не ограничивается. Например, с их помощью можно моделировать связи между:

13 <ul><li>веб-страницами;</li>

14 <li>улицами и перекрёстками при проектировании дорожной сети;</li>

15 <li>генами, белками и молекулами в биоинформатике;</li>

16 <li>пунктами доставки грузов в логистике;</li>

17 <li>точками передвижения роботов в робототехнике.</li>

18 </ul>Идея алгоритма Дейкстры в том, что мы можем найти наименьшие расстояния от начальной вершины графа ко всем остальным. Зная эти расстояния, можно построить кратчайший маршрут между начальной и другими точками.

19 Допустим, у нас есть несколько городов, соединённых дорогами. Назовём их А,B,C,D,E,F. Числа возле рёбер - расстояния между городами в милях.

20 Инфографика: Майя Мальгина для Skillbox MediaТеперь попробуем найти кратчайший маршрут, скажем, от A до C. Как это сделать? Вроде бы несложно: сравниваем все возможные пути и выбираем самый короткий:A → B → C. Банальный перебор, совсем не rocket science.

21 Сложности начинаются, когда данных становится слишком много. Если бы городов на нашей карте было больше 26, даже самому мощному компьютеру<a>понадобилось бы</a>несколько миллиардов лет, чтобы просчитать все варианты.

22 Алгоритм Дейкстры работает иначе: он не перебирает "в уме" все возможные варианты, а строит маршрут пошагово. На каждом шаге алгоритм выбирает наименее отдалённую вершину и двигается к ней, затем к следующей - и так, пока не доберётся до цели.

23 Ключевой смысл такой: если на каждом этапе принимать оптимальные решения, то и конечное решение, скорее всего, тоже окажется оптимальным. Алгоритмы которые работают по такому принципу, называются жадными.

24 Вернёмся к нашему графу с городами. Найдём с помощью алгоритма Дейкстры кратчайшие расстояния от А доB,C,D,E иF.

25 Шаг 1.Установим для каждой вершины первоначальную оценку пути до А. Для самойА оценка равна0, остальным присвоим бесконечность, так как мы пока не знаем их значения.

26 Инфографика: Майя Мальгина для Skillbox MediaРассмотрим соседние с Aвершины - то есть те, которые связаны с Арёбрами напрямую. ЭтоBиE -их расстояния до Аравны7и 4соответственно. Так как эти значения, очевидно, меньше бесконечности, обновим их на схеме. ВершинуАбудем считать посещённой - закрасим её и больше не рассматриваем.

27 Инфографика: Майя Мальгина для Skillbox MediaТеперь перейдём к непосещённой вершине с наименьшим расстоянием до А. Это вершинаE. Соседние с ней непосещённые вершины -Fи D. Их расстояния до Абудут равны оценкеE(то есть расстоянию от E до А) плюс веса рёбер от Eдо этих вершин. Получается так:

28 <ul><li>ДляF: 4 + 3 = 7</li>

29 <li>ДляD: 4 + 8 = 12</li>

30 </ul>Полученные расстояния меньше предыдущих оценок, поэтому запишем их возле вершинFиD. ВершинуEбудем считать посещённой. Закрасим её.

31 Инфографика: Майя Мальгина для Skillbox MediaДальше по аналогии: алгоритм выбирает непосещённые вершины с наименьшей оценкой и считает расстояния от соседних с ней вершин до А. И продолжается это до тех пор, пока алгоритм не вычислит кратчайшие расстояния до Адля всех вершин.

32 Инфографика: Майя Мальгина для Skillbox MediaГотово! Теперь мы можем построить кратчайший маршрут от Адо любой другой вершины. Например:

33 <ul><li>От Aдо F:A - E - F</li>

34 <li>От A доD: A - E - D</li>

35 <li>От A до C: A - B - C</li>

36 </ul>Но у алгоритма Дейкстры есть и ограничения: во-первых, он работает только со взвешеннымиграфами - то есть такими, где веса между рёбрами известны заранее. А во-вторых, эти расстояния должны быть неотрицательными.

37 Алгоритм поиска кратчайшего пути разработал голландский учёный Эдсгер Дейкстра в 1956 году. В то время он искал способ продемонстрировать возможности нового компьютера ARMAC и искал задачу, которую мог бы решить ARMAC и при этом понятную незнакомым с компьютерами людям.

38 Дейкстра взял задачу поиска кратчайшего пути и разработал алгоритм её решения. На базе алгоритма он разработал программу построения маршрутов между городами по транспортной карте Нидерландов.

39 Позже Дейкстра рассказывал:

40 "Однажды мы с моей невестой пили кофе на террасе кафе в Амстердаме. Там я примерно за двадцать минут разработал алгоритм нахождения кратчайшего пути. Он был опубликован через три года, в 1959 году.

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

42 Этот алгоритм стал, к моему удивлению, одним из краеугольных камней моей славы".

43 Эдсгер Дейкстрав интервью Филиппу Л. Франа

44 С теорией разобрались - теперь давайте напишем код, реализующий алгоритм Дейкстры на языке Python. В качестве примера рассчитаем расстояние от вершиныAдо других вершин в нашем графе.

45 Для работы нам понадобится heapq - один из модулей стандартной библиотеки Python, предназначенный для работы с кучами. Куча - структура данных, где каждый родительский узел имеет значение, меньшее или равное любому из его дочерних элементов.

46 Создадим функцию dijkstra с аргументами:

47 graph - заданный граф;

48 start - начальная вершина.

49 Внутри функции создаём словарь distances, чтобы хранить расстояния от начальной вершины до всех остальных. Мы также создаём кучу priority_queue для выбора вершин с наименьшим текущим расстоянием.

50 import heapq def dijkstra(graph, start): # Инициализация словаря для хранения расстояний # до каждой вершины. Сначала все расстояния бесконечны. distances = {vertex: float('infinity') for vertex in graph} # Расстояние до начальной вершины равно 0. distances[start] = 0 # Создаём приоритетную очередь для хранения вершин и их расстояний. priority_queue = [(0, start)]Далее алгоритм в цикле обновляет расстояния до соседних вершин до тех пор, пока не найдёт кратчайшие расстояния для всех вершин. Результат выводится в виде словаря, где ключи - вершины, а значения - расстояния до них от точкиA.

51 while priority_queue: # Извлекаем вершину с наименьшим расстоянием из очереди. current_distance, current_vertex = heapq.heappop(priority_queue) # Если текущее расстояние до вершины уже больше, чем сохранённое расстояние, игнорируем её. if current_distance > distances[current_vertex]: continue # Рассмотрим все соседние вершины текущей вершины. for neighbor, weight in graph[current_vertex].items(): distance = current_distance + weight # Если найден более короткий путь до соседа, обновим расстояние. if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(priority_queue, (distance, neighbor)) return distancesТеперь рассчитаем для нашего графа кратчайшие расстояния от Адо остальных вершин. Граф представим в виде словаря, где ключи - вершины, а значения - словари с соседними вершинами и весами рёбер.

52 # Пример использования: graph = { 'A': {'B': 4, 'C': 7}, 'B': {'A': 4, 'D': 2, 'E': 8}, 'C': {'A': 7, 'D': 2, 'E': 5}, 'D': {'B': 2, 'C': 2, 'E': 1,'F': 4}, 'E': {'C': 5, 'D': 1, 'F': 11}, 'F': {'B': 8, 'D': 4, 'E': 11} }Вызываем функцию dijkstra с начальной вершинойAи выводим в консоль результат.

53 result = dijkstra(graph, 'A') # Выводим результат. print("Кратчайшие расстояния до каждой вершины:") for vertex, distance in result.items(): print(f"До вершины {vertex}: {distance}")Бинго!

54 Кратчайшие расстояния до каждой вершины: До вершины A: 0 До вершины B: 4 До вершины C: 7 До вершины D: 6 До вершины E: 7 До вершины F: 10Другой известный алгоритм для поиска кратчайшего пути - A* (читается как "А звезда" или "А стар"). По сути, это расширение алгоритма Дейкстры с дополнительными функциями для улучшения скорости. Разработали A* в 1968 году, используют - до сих пор в разных областях: от робототехники до навигации и геймдева.

55 Так же как и алгоритм Дейкстры, A* ищет расстояние от начальной точки до конечной. Но, в отличие от последнего, он учитывает не только расстояние от текущей точки до начальной, но и эвристическую оценку этого расстояния. В данном контексте "эвристическая" означает "примерная": функция не определяет точное расстояние от точки до цели, но подсказывает алгоритму приблизительную величину.

56 Например, нам нужно найти кратчайший путь из города А в город В на карте. В качестве эвристики мы можем использовать расстояние "по прямой линии" (то есть "евклидово расстояние") от текущей точки до точки B. Это позволит оценить длину пути между текущей точкой и целью.

57 Изображение: Skillbox MediaНа графике выше изображены эвристические расстояния от промежуточных точек до конечной точки на карте, без учёта существующих дорог.

58 Ещё одна популярная эвристика - манхэттенское расстояние. Её название происходит от системы улиц на острове Манхэттен в Нью-Йорке. Это сеть улиц, которые пересекаются под прямым углом, что делает её похожей на таблицу. Чтобы добраться от одной точки до другой, приходится двигаться вдоль улиц. Если представить эти улицы в виде координатной сетки, мы можем двигаться только вдоль осей X и Y, но не по диагонали.

59 Если у нас есть две точки с координатами (x1,y1) и (x2,y2), то манхэттенское расстояние между ними (M) вычисляется по следующей формуле:

60 Изображение: Skillbox MediaПопробуем разобраться на примере. Допустим, у нас есть точкаA с координатами (2, 8) и точкаB с координатами (4, 3).

61 Изображение: Skillbox MediaПодставляем координаты в формулу - получается, манхэттенское расстояние равно M = ∣4-2∣ + ∣3-8∣ = 2 + 5 = 7.

62 Основная идея алгоритма A* - это определение двух значений для каждой вершины в графе:

63 <ul><li>g(n) - длина пути от начальной вершины до текущей вершины n.</li>

64 <li>h(n) - эвристическая оценка длины от текущей вершины n до цели.</li>

65 </ul>На каждом шаге алгоритм A* выбирает вершину с наименьшей суммойg(n) + h(n)и исследует её соседей. Это продолжается до тех пор, пока алгоритм не достигнет конечной цели.

66 Попробуем написать A* на Python для графа с эвристикой в виде манхэттенского расстояния. Здесь функция manhattan_distance вычисляет манхэттенское расстояние между двумя точками, а astar реализует алгоритм A* с использованием этого расстояния.

67 import heapq # Функция для вычисления манхэттенского расстояния между двумя точками def manhattan_distance(point1, point2): return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1])Реализация алгоритма A*:

68 def astar(grid, start, goal): # Инициализация словарей для хранения стоимостей и предыдущих точек cost = {start: 0} came_from = {start: None} # Приоритетная очередь для хранения точек и их оценок (приоритетов) priority_queue = [(0, start)] while priority_queue: # Извлечение точки с минимальной оценкой current_cost, current_point = heapq.heappop(priority_queue) # Если достигнута целевая точка, завершаем алгоритм if current_point == goal: break # Рассмотрение соседних точек for neighbor in [(1, 0), (-1, 0), (0, 1), (0, -1)]: x, y = current_point[0] + neighbor[0], current_point[1] + neighbor[1] new_cost = cost[current_point] + 1 # Стоимость перемещения на одну ячейку # Проверка на наличие препятствия и обновление стоимости, если новый путь короче if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == 0: if (x, y) not in cost or new_cost < cost[(x, y)]: cost[(x, y)] = new_cost priority = new_cost + manhattan_distance((x, y), goal) # Оценка для приоритета heapq.heappush(priority_queue, (priority, (x, y))) came_from[(x, y)] = current_pointВосстановление пути:

69 path = [] current = goal while current: path.append(current) current = came_from[current] path.reverse() return pathВыполнение алгоритма A*. Определение сетки 5 × 5. Препятствия обозначаются единицами в сетке.

70 grid = [ [0, 0, 0, 0, 0], [0, 1, 1, 0, 0], [0, 0, 0, 1, 0], [0, 1, 0, 0, 0], [0, 0, 0, 0, 0] ] # Начальная и конечная точки start = (0, 0) goal = (4, 4) result_path = astar(grid, start, goal) # Вывод результата print("Путь от A до B:") for point in result_path: print(point)В результате выполнения получим:

71 Путь от A до B: (0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (1, 4) (2, 4) (3, 4) (4, 4)Этот код реализует A* для поиска кратчайшего пути в заданной сетке с использованием манхэттенского расстояния в качестве эвристической функции. В результате он выводит кратчайший путь от точкиАдо B.

72 Выбор между этими алгоритмами зависит от конкретной задачи и доступной информации.

73 Сравним их:

74 <ul><li>Алгоритм Дейкстры используется для нахождения кратчайшего пути от начальной вершины графа ко всем остальным. Алгоритм A* используется для нахождения кратчайшего пути от начальной вершины к заданной, учитывая эвристическую оценку расстояния.</li>

75 <li>Алгоритм Дейкстры рассматривает все вершины равнозначно и всегда выбирает вершину с наименьшим расстоянием до неё. Алгоритм A*, кроме этого, дополнительно использует эвристику. Это делает его более эффективным для больших графов или когда есть информация о приблизительной величине дистанции до цели.</li>

76 <li>Алгоритм Дейкстры может быть медленным для больших графов, так как исследует все вершины. Алгоритм A* в больших графах работает быстрее благодаря эвристике, которая позволяет сократить количество рассматриваемых вершин.</li>

77 </ul>Таким образом, алгоритм Дейкстры будет эффективнее там, где нужно найти кратчайшие пути от одной вершины ко всем остальным и нет информации о примерной дистанции до цели. Если есть эвристическая информация, которая может помочь ускорить поиск, то лучшим выбором будет A*.

78 <a>Бесплатный курс по Python ➞Мини-курс для новичков и для опытных кодеров. 4 крутых проекта в портфолио, живое общение со спикером. Кликните и узнайте, чему можно научиться на курсе. Смотреть программу</a>