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

Алгоритм Дейкстры (Dijkstra) предназначен для решения задачи поиска кратчайших путей в графе.

Суть

Важным фактом, позволяющим исключить перебор, является то, что если у нас есть кратчайший путь от v до w, проходящий через вершину y, назовем его $(v \rightarrow w)^*$, то его первая часть от v до y, $(v \rightarrow y)^*$, тоже будет кратчайшим путем. Действительно, если бы это было не так, то есть существовал бы путь $(v \rightarrow y)^!$ длины меньшей, чем $(v \rightarrow y)^*$, то можно было бы улучшить оптимальный путь $(v \rightarrow w)^*$, заменив в нем $(v \rightarrow y)^*$ на $(v \rightarrow y)^!$ (См. #Рисунок 1).

В алгоритме Дейкстры мы итерационно поддерживаем два множества вершин:

Visited

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

ToVisit

множество вершин, которые достижимы одним ребром из множества вершин Visited, ассоциированных с верхними оценками стоимости пути до них.

На каждой итерации, мы выбираем из достижимых вершин вершину v, самую ближайшую к стартовой вершине s, и переносим ее из множества ToVisit в множество Visited, увеличиваем множество «кандидатов» ToVisit ее соседями, и пересчитываем верхнюю оценку удаленности вершин из ToVisit до вершины s.

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

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

Код алгоритма, представлен в виде функции на языке Python.

def dijkstra(G,start_node):
    # хэш (узел -> стоимость) посещенных вершин
    Visited={}               
    # хэш (узел -> стоимость) ближайших к посещенным
    ToVisit={start_node:0}          
    # хэш (узел -> кратчайший путь)
    Paths = {start_node:[start_node]}   
    # пока есть вершины, до которых не построен кратчайший путь
    while ToVisit:  
        # выбираем ближайшую
        v=argmin(ToVisit)       
        # до $v$ кратчайший путь найден
        Visited[v]=ToVisit[v]; del ToVisit[v];   
        # для всех соседей вершины $v$
        for w in G.neighbors(v): 
            # к которым еще не нашли кратчайший путь     
            if (w not in Visited):  
                # обновляем кратчайшие пути
                vwLength = Visited[v] + G.get_edge(v,w) 
                if (w not in ToVisit) or (vwLength < ToVisit[w]):
                    ToVisit[w] = vwLength
                    Paths[w] = Paths[v]+[w]
        print_frame(G, start_node, Visited, ToVisit, Paths) 
    return (Visited,Paths)

Трассировка алгоритма

Последовательность итераций алгоритма показана ниже. В голубой цвет выкрашены вершины из «Visited» (причем указана стоимость их достижения), в желтый — из «ToVisit» (указана минимально известная стоимость их достижения для данной итерации). Также выделены ребра, принадлежащие кратчайшим путям.

Итерация 1

Итерация 2

Итерация 3

Итерация 4

Итерация 5

Итерация 6

Итерация 7

Рисунок 1

По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.