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

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

Важным фактом, позволяющим исключить перебор, является то, что если у нас есть кратчайший путь от v до w, проходящий через вершину y, назовем его , то его первая часть от v до y, , тоже будет кратчайшим путем. Действительно, если бы это было не так, т.е. существовал бы путь длины меньшей, чем , то можно было бы улучшить оптимальный путь , заменив в нем на .

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

Visited

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

ToVisit

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

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

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

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

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

# Находит кратчайшие пути из одной вершины 
# во все остальные.
def dijkstra(G,s):
    print "StartVertice:",s
    # хэш-таблица вершин, до которых построены кратчайшие пути, (узел:стоимость)
    Visited={}                  
    # хэш-таблица вершин, до которых еще не построены кратчайшие пути, (узел:стоимость)
    ToVisit={s:0}
    Paths = {s:[s]}   # хэш-таблица (узел:кратчайший путь)
    while ToVisit:  # пока есть вершины, до которых не построен кратчайший путь
        print Visited, ToVisit, "-------->",
        v=argmin(ToVisit)       # выбираем ближайшую
        Visited[v]=ToVisit[v]; del ToVisit[v];   # считаем, что до нее кратчайший путь найден
        for w in G.neighbors(v): # для всех соседей вершины $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 Visited, ToVisit
    print Visited, Paths    
    return (Visited,Paths)

StartVertice: 2
{} {2: 0} --------> {2: 0} {1: 15, 3: 20, 4: 15}
{2: 0} {1: 15, 3: 20, 4: 15} --------> {1: 15, 2: 0} {0: 75, 3: 20, 4: 15}
{1: 15, 2: 0} {0: 75, 3: 20, 4: 15} --------> {1: 15, 2: 0, 4: 15} {0: 75, 3: 20}
{1: 15, 2: 0, 4: 15} {0: 75, 3: 20} --------> {1: 15, 2: 0, 3: 20, 4: 15} {0: 70}
{1: 15, 2: 0, 3: 20, 4: 15} {0: 70} --------> {0: 70, 1: 15, 2: 0, 3: 20, 4: 15} {}
{0: 70, 1: 15, 2: 0, 3: 20, 4: 15} {0: [2, 3, 0], 1: [2, 1], 2: [2], 3: [2, 3], 4: [2, 4]}

---

Репликация: База Знаний «Заказных Информ Систем» → «Алгоритм Дейкстры»

Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».