Алгоритм Дейкстры — различия между версиями

Текущая версия на 16:47, 23 октября 2008

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

Важным фактом, позволяющим исключить перебор, является то, что если у нас есть кратчайший путь от v до w, проходящий через вершину y, назовем его , то его первая часть от v до 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» (указана минимально известная стоимость их достижения для данной итерации). Также выделены ребра, принадлежащие кратчайшим путям.