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

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

Алгоритм Дейкстры (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[править]

Graph image creation requires permission to upload.

Итерация 2[править]

Graph image creation requires permission to upload.

Итерация 3[править]

Graph image creation requires permission to upload.

Итерация 4[править]

Graph image creation requires permission to upload.

Итерация 5[править]

Graph image creation requires permission to upload.

Итерация 6[править]

Graph image creation requires permission to upload.


Итерация 7[править]

Graph image creation requires permission to upload.

Рисунок 1[править]

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