Алгоритм Дейкстры – что это такое

Кем и когда был разработан

Алгоритм Дейкстры был разработан голландским ученым Эдсгером Дейкстрой в 1959 году. Интересно отметить, что разработка этого алгоритма произошла в контексте его работы над системой программирования для ЭВМ EDSAC (Electronic Delay Storage Automatic Calculator) в Университете Кембриджа.

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

Впервые алгоритм был описан в письменной форме в статье Дейкстры «A Note on Two Problems in Connexion with Graphs» («Замечание по двум проблемам, связанным с графами»), опубликованной в журнале Numerische Mathematik в 1959 году. В этой статье ученый представил алгоритм, который стал известен как алгоритм Дейкстры, предназначенный для нахождения кратчайших путей в графах с неотрицательными весами ребер.

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

Реализация алгоритма Дейкстры на Python

Приведем несложный пример простой реализации алгоритма Дейкстры на языке Python. Здесь предполагается, что граф представлен в виде словаря с весами ребер:

import heapq

def dijkstra(graph, start):

# Инициализация расстояний: начальная вершина — 0, остальные — бесконечность

distances = {vertex: float(‘infinity’) for vertex in graph}

distances[start] = 0

# Инициализация очереди с приоритетом (куча)

priority_queue = [(0, start)]

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

# Пример использования

graph_example = {

‘A’: {‘B’: 1, ‘C’: 3},

‘B’: {‘A’: 1, ‘D’: 2, ‘E’: 1},

‘C’: {‘A’: 3, ‘E’: 5, ‘F’: 4},

‘D’: {‘B’: 2, ‘E’: 1},

‘E’: {‘B’: 1, ‘C’: 5, ‘D’: 1, ‘F’: 3},

‘F’: {‘C’: 4, ‘E’: 3}

}

start_vertex = ‘A’

result = dijkstra(graph_example, start_vertex)

print(f»Кратчайшие расстояния от вершины {start_vertex}: {result}»)

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

Что такое алгоритм А*

Алгоритм A (A-star)* – это эффективный алгоритм поиска кратчайшего пути в графе, который сочетает в себе идеи жадного поиска и алгоритма Дейкстры. А* был разработан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем.

Главной особенностью алгоритма A* является использование эвристической функции (или оценочной функции), которая приближенно оценивает стоимость достижения целевой вершины из текущей. Эта эвристика добавляется к стоимости пути от начальной вершины, что позволяет алгоритму «приоритизировать» пути, которые, вероятно, будут ближе к оптимальным.

Основные шаги алгоритма A*:

• Установка начальной вершины и целевой вершины.
• Инициализация пустых списков открытых и закрытых вершин.
• Установка стоимости пути от начальной вершины до текущей.
• Вычисление эвристической оценки стоимости от текущей вершины до целевой.
• Добавление текущей вершины в открытый список.
• Выбор вершины из открытого списка с наименьшей суммой стоимости пути и эвристической оценки.
• Проверка, является ли текущая вершина целевой. Если да, завершение.
• Для каждой соседней вершины текущей вершины обновление стоимости пути, если новый путь короче; вычисление новой эвристической оценки; если вершина не в открытом списке, добавление ее туда.
• Перемещение текущей вершины из открытого списка в закрытый.
• Повторение шагов до достижения целевой вершины или исчерпания возможных путей.
• Восстановление кратчайшего пути от целевой вершины до начальной.

Алгоритм A* широко применяется в робототехнике, компьютерных играх, маршрутизации и других областях, где требуется эффективный поиск оптимальных путей.

Реализация А* на Python

Приведем пример простой реализации алгоритма A* на языке Python. Предполагается, что граф представлен в виде словаря с весами ребер и координатами вершин:

import heapq

import math

def heuristic(node, goal):

# Эвристическая функция (в данном случае — эвклидово расстояние между вершинами)

return math.sqrt((node[0] — goal[0])**2 + (node[1] — goal[1])**2)

def astar(graph, start, goal):

# Инициализация начальной вершины

open_set = [(0, start)]

came_from = {}

g_score = {start: 0}

while open_set:

current_score, current_node = heapq.heappop(open_set)

if current_node == goal:

path = []

while current_node in came_from:

path.insert(0, current_node)

current_node = came_from[current_node]

path.insert(0, start)

return path

for neighbor in graph[current_node]:

tentative_g_score = g_score[current_node] + graph[current_node][neighbor]

if neighbor not in g_score or tentative_g_score < g_score[neighbor]:

g_score[neighbor] = tentative_g_score

f_score = tentative_g_score + heuristic(neighbor, goal)

heapq.heappush(open_set, (f_score, neighbor))

came_from[neighbor] = current_node

return None

# Пример использования

graph_example = {

(0, 0): {(0, 1): 1, (1, 0): 1},

(0, 1): {(0, 0): 1, (1, 1): 1},

(1, 0): {(0, 0): 1, (1, 1): 1},

(1, 1): {(0, 1): 1, (1, 0): 1}

}

start_vertex = (0, 0)

goal_vertex = (1, 1)

result = astar(graph_example, start_vertex, goal_vertex)

print(f»Кратчайший путь от {start_vertex} до {goal_vertex}: {result}»)

В этом коде реализован алгоритм A* для поиска кратчайшего пути в графе. Путь выводится в виде последовательности вершин от начальной до конечной.

В чем разница

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

Эвристическая функция

• Дейкстра: не использует эвристическую функцию. Рассматривает все возможные пути равнозначно.
• A*: использует эвристическую функцию для оценки стоимости достижения целевой вершины из текущей. Это позволяет алгоритму эффективно направлять поиск в сторону потенциально более оптимальных путей.

Оценка времени выполнения

• Дейкстра: гарантированно находит кратчайший путь во взвешенных графах, но неэффективен, если все веса ребер положительны.
• A*: стремится найти оптимальный путь, но может быть эффективнее Дейкстры благодаря эвристической функции, особенно в случае больших графов.

Применимость

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

Требования к памяти

• Дейкстра: требует O(|V|^2) памяти для хранения расстояний между всеми парами вершин, где |V| — количество вершин.
• A*: требует O(|V|) памяти для открытого и закрытого списка вершин, но может быть более требователен к памяти при использовании сложных эвристических функций.

Итак, как выбрать между алгоритмом Дейкстры и A*?

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

В целом, выбор зависит от конкретных требований вашей задачи, размеров графа и особенностей структуры данных.