Главная Блог Алгоритм Дейкстры – что это такое

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

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

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

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

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

Принцип работы алгоритма Дейкстры

Для каждой вершины графа устанавливается начальное расстояние от исходной вершины (назовем ее A). Для A расстояние устанавливается как 0, а для всех остальных – бесконечность. Также создается список посещенных вершин, изначально пустой.

Пусть дан граф:


A

/ \

B   C

/ \ / \

D — E – F


С начальной вершиной A и весами ребер: AB=1, AC=3, BD=2, BE=1, CE=5, CF=4, DE=1, EF=3.

Результат: кратчайшие расстояния от A – A(0), B(3), C(8), D(4), E(2), F(5).

Среднее время реакции на обращение: 13,5 мин.
Среднее время решения задачи: 1 час 21 мин.

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

Алгоритм Дейкстры был разработан голландским ученым Эдсгером Дейкстрой в 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* для поиска кратчайшего пути в графе. Путь выводится в виде последовательности вершин от начальной до конечной.

 

90% клиентов пришли к нам по рекомендации

В чем разница

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

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

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

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

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

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

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

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

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

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

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

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

Остались вопросы?

Оставьте заявку и наш менеджер свяжется с Вами в течение 15 минут

    Надоели непредвиденные
    расходы на ИТ?

    • Гарантируем фиксированную стоимость обслуживания на 2 года по договору
    • Включаем в тариф неограниченное количество экстренных вызовов
    • Первый месяц обслуживания за наш счет
    Рассчитать стоимость аутсорсинга
    Нажимая кнопку «Отправить», я даю свое согласие на обработку моих персональных данных, в соответствии с Федеральным законом от 27.07.2006 года №152-ФЗ «О персональных данных», на условиях и для целей, определенных в Соглашении на обработку персональных данных