Текст:Поиск кратчайших путей: алгоритм Дейкстры

Алгоритм Дейкстры (Dijkstra) предназначен для решения задачи поиска кратчайших путей в графе — Shortest Path Problem: Заданы n вершин графа (узлов сети) $v_1,v_2,\ldots,v_n$ и положительные целые длины дуг $d_{ij} \equiv d(v_i,v_j)$ между ними. Чему равна наименьшая возможная длина пути, ведущего из $v_1$ в $v_k$, для всех $k \in (2 \ldots n)$?

Важным фактом, позволяющим исключить перебор, является то, что если у нас есть кратчайший путь от 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)^!$.

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

Visited

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

ToVisit

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

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

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

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

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

<code-python>

1. Находит кратчайшие пути из одной вершины
2. во все остальные.

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)

</code-python>

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]}

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