Алгоритм Эдсгера Дейкстры.

Nov 11, 2024

Алгоритмы это важно ! Возможно их не так часто приходится применять на практике, но этот скилл просто должен быть у каждого кто кодит. Это константы, догма и библия, правила дорожного движения. Или еще важнее. В общем - очень надо!

Алгоритм Эдсгера Дейкстры (1959 год)

или просто "Алгорит Дейкстры"

Допустим что мы имеем: Направленный (Ориентированный) Ациклический Граф или Direct Acyclic Graph как говорят англичане. Представим в нем ребра и вершины:

[Start] >> [A] = 4
[Start] >> [B] = 1
[Start] >> [Finish] = 6
[B] >> [F] = 3
[B] >> [C] = 2
[A] >> [C] = 2
[C] >> [F] = 2

Алгоритм Дейкстры решает задачу поиска кратчайшего пути на 'взвешенных графах'. То есть когда мы имеем значение - "вес ребра", это может означать практически любые данные, расстояние, затрачиваемое время, съеденные каллории, потраченый рессурс, и так далее.

У нас есть ограничения:

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

Декомпозиция задачи:

  • Найти узел с наименьшим весом.
  • Проверить, существует ли путь к соседним узлам "легче".
  • Обойти с проверкой по всем узлам (нодам).
  • Вычислить итоговый путь.

Инициируем Python dict() с нодами.

graph = {}
graph['start'] = {}
graph['a'] = {}
graph['b'] = {}
graph['fin'] = {}

Сам граф и его ребра с весами:

graph['start']['a'] = 6
graph['start']['b'] = 2
graph['a']['fin'] = 1
graph['b']['a'] = 3
graph['b']['fin'] = 5
  • От старта к А
  • От старта к В
  • От А к финишу
  • От В к А
  • От В к финишу

Начальные данные указывающие стоймость пути:

costs = {}
costs['a'] = 6
costs['b'] = 2
costs['fin'] = float('inf')

Узлы и их родительские узлы:

parents = {}
parents['a'] = "start"
parents['b'] = "start"
parents['in'] = None

Пустой Python List для результирующего маршрута.

processed = list()

Эта функция нам поможет найти самый легкий вес.

def find_low_cost(costs): 
    lowest = float('inf') 
    lowest_node = None 
    for node in costs: 
        cost = costs[node]  
        if cost < lowest and node not in processed: 
            lowest = cost
            lowest_node = node
    return lowest_node

Основной блок кода.

node = find_low_cost(costs)
while node is not None:
    cost = costs[node]
    neighbors = graph[node]
    for nei in neighbors.keys():
        new_cost = cost + neighbors[nei]
        if costs[nei] > new_cost:
            costs[nei] = new_cost
            parents[nei] = node
    processed.append(node)
    node = find_low_cost(costs)

Ну и в самом конце "принтанем" наш результирующий набор.

print(processed)

Пример логического решения другой задачи с взвешенным графом:

Допустим мы имеем граф

Его вершины и веса:

ST >> A = 4
ST >> B = 1
ST >> F = 6
B >> F = 3
B >> C = 2
A >> C = 2
C >> F = 2

Для работы нам нужна структура в виде таблицы данных где мы будем хранить вычисления.

Начинаем от старта к любому, из наших трех начальных ребер: ST >> A , ST >> B , ST >> F

Первая итерация, кладем в очередь - вершину, вес ребра, и вершину предшественник.

Как выгдядит это:

Обходим ST >> A = 4, ST >> B = 1, ST >> F = 6 Важно что в очереди на выход/обработку первым - самый легкий вес, то есть первый на извлечение и обход к следующим вершинам.

*В примере с кодом выше, в роли таблицы с очередью я использовал python dictionary - parents, neighbors, costs. В случае примера с кодом такое решение наиболее подходящее. Безусловно есть и другие способы решить как хранить и обрабатывать подобные данные.

 ------------------------------------
| предшественник   | вершина   | вес |
--------------------------------------
| ST               | B         | 1   |
--------------------------------------
| ST               | A         | 4   |
--------------------------------------
| ST               | F         | 6   |
--------------------------------------

Первым извлекаем ST >> B который весит 1, он у нас самый легкий и поэтому работаем с ним первым.

B >> C = 2 + вес ребра предшественника, он у нас = 1. То есть мы на прошлой релаксации определили вес ребра до вершины В.

Следовательно B >> F = 3 + вес предшественника = 1

И далее работаем по тому же алгоритму...

------------------------------------
| предшественник   | вершина   | вес |
--------------------------------------
| B                | C         | 3   |
--------------------------------------
| B                | F         | 4   |
--------------------------------------

Больше смежных ребер у B нет ! Следовательно переходим к другим, извлекаем из очереди самый легкий!

Дальше переходим к C >> F = 5.

Ребро до F не станем переписывать, оно тяжелее чем уже имеющееся значение B >> F = 4 Возвращаемся к тем ребрам которые не иследованы.

A >> C = 2 + 4 от ST >> A = 6 - Не будем переписывать значение C = 6 потому что есть путь легче S >> B >> C.

Оставим C весом 3, а его предшественник B

C >> F = 2 + У узла C уже было значение 3 от ребер SТ >> B >> C, что в сумме дает вес 5,

но мы знаем что до F мы доберемся за вес меньше 4 по ребрам от SТ >> B >> F

Так мы обошли все вершины, и нашли самый легкий путь от стартового - SТ, через - B, к - F финишу.

Короткое но должно быть вполне понятное объяснение происходящего в процессе работы алгоритма.

Ivan Goncharov