Алгоритм Дейкстры
Алгори́тм Де́йкстры (Dijkstra’s algorithm) — алгоритм поиска пути на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных или до заданной конечной. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.
Принцип работы
Каждой вершине сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.
Шаг алгоритма. Если доступные вершины посещены, алгоритм завершается. В противном случае, выбирается одна из непосещённых вершин Для каждого соседа данной вершины, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений пути от начала до вершины (метки вершины) и длины ребра, соединяющего её с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину как посещенную и повторим шаг алгоритма для другой вершины.
Эффективность алгоритма
В области нахождения пути от конкретной вершины графа до всех его вершин алгоритм Дейкстры является лучшим на данный момент.
Данный алгоритм также отлично справляется с поиском пути только между 2 вершинами на графе, в котором невозможно составить эвристическую функцию, находящую примерное расстояние между двумя его вершинами (текущей и конечной).
В противном случае, алгоритм Дейкстры по всем параметрам уступает своей модификации – алгоритму A*(A-star, см. подраздел «АлгоритмA*»). Причиной различий служит то, что алгоритм Дейкстры будет проверять узлы графа равномерно в порядке удаления от начального, аA* отдаёт предпочтения тем узлам, которые по результатам эвристических расчётов ближе к конечному узлу, а значит, с большей вероятностью, будут принадлежать конечному пути. Таким образом, за счёт использования не затратной эвристической функции,A* будет проверять не больше, а на практике – значительно меньше узлов графа, чем алгоритм Дейкстры, а значит, будет работать быстрее.
Практика
Ниже представлен алгоритм Дейкстры для взвешенного графа, реализованный на языке Python2.7
Для начала, следует определиться со способом хранения взвешенного графа. Актуальная информация для хранения – узлы, связи, вес связей. В Pythonпредпочтительным мне кажется вариант хранения этой информации при помощи «Словарей». Словарь, по сути, является аналогом массива, в котором вместо индекса выступает ключ.
Таким образом, граф будет представлен словарём словарей, где:
- сама структура отображает граф в целом;
- ключи внешнего словаря являются узлами графа;
- значения по этим ключам являются множеством связей графа;
- ключи в этом множестве являются конечными точками связей, выходящих из данного узла;
- значения множества связей по данным ключам являются весом таких связей.
Изобразим полученный граф схематически:
Создадим для примера простой граф по этой схеме:
>>> graph={
'A': {'B': 2, 'D': 4},
'C': {'B': 4, 'F': 2},
'B': {'A': 2, 'C': 4, 'D': 3},
'E': {'D': 9, 'F': 3},
'D': {'A': 4, 'B': 3, 'E': 9},
'F': {'C': 2, 'E': 3}}
Таким образом, узлы графа вызываются встроенным в словарь методом keys():
>>> graph.keys()
['A', 'C', 'B', 'E', 'D', 'F']
Или простым пробегом цикла for:
>>> for i in graph:
print i
A
C
B
E
D
F
Рёбра, исходящие из заданного узла можно вывести, просто применив к внешнему словарю в качестве ключа данный узел:
>>> print graph['D']
{'A': 4, 'B': 3, 'E': 9}
Вес данных связей можно получить, вызвав множество рёбер узла, из которого исходит связь по ключу – конечному узлу связи:
>>> print graph['D']['B']
3
Также, данный способ делает возможным описывать несколько более сложные структуры, например орграф (граф, рёбра которого имеют помимо веса направление и актуальны только в этом направлении) .
Создадим для дальнейших применений алгоритма Дейкстры схожий с предыдущим графф, у которого связь C-F будет актуальна только от C к F:
>>> graph2={
'A': {'B': 2, 'D': 4},
'C': {'B': 4, 'F': 2},
'B': {'A': 2, 'C': 4, 'D': 3},
'E': {'D': 9, 'F': 3},
'D': {'A': 4, 'B': 3, 'E': 9},
'F': {'E': 3}}
Схема данного орграфа:
Теперь перейдём к самому алгоритму Дейкстры. Данный алгоритм будет описан как для нахождения кратчайшего пути между 2 точками, так и для нахождения такого пути от заданной точки ко всем точкам графа. Ниже следует описание алгоритма Дейкстры для поиска пути между 2 точками графа:
def Dijkstra(graph,start,end):
class NodeRecord:
node=None
connection=None
costSoFar=None
startRecord =NodeRecord()
startRecord.node = start
startRecord.connection = None
startRecord.costSoFar = 0
olist= [startRecord]
clist = []
while len(olist) > 0:
tlist=[i.costSoFar for i in olist]
current=olist[tlist.index(min(tlist))]
if current.node == end:
break
connections = graph[current.node]
for connection in connections:
endNode = connection
endNodeCost = current.costSoFar + graph[current.node][connection]
if endNode in [clist[ite].node for ite in range(len(clist))]:
endNodeRecord = clist[[clist[ite].node for ite in range(len(clist))].index(endNode)]
if endNodeRecord.costSoFar <= endNodeCost:
continue
clist.pop(clist.index(endNodeRecord))
elif endNode in [olist[ite].node for ite in range(len(olist))]:
endNodeRecord = olist[[olist[ite].node for ite in range(len(olist))].index(endNode)]
if endNodeRecord.costSoFar <= endNodeCost:
continue
else:
endNodeRecord = NodeRecord()
endNodeRecord.node = endNode
endNodeRecord.costSoFar = endNodeCost
endNodeRecord.connection = current
if not endNodeRecord in olist :
olist.append(endNodeRecord)
clist.append(current)
olist.pop(olist.index(current))
else:
return -1
path = [end]
while current.node!=start:
current=current.connection
path.insert(0,current.node)
return path
Основное отличие данного алгоритма от классического описания алгоритма Дейкстры заключается в том, что вместо создания статического массива необработанных вершин графа используются динамические списки тех вершин, которые, не будучи обработанными, имеют связи с уже обработанными вершинами. Такой приём позволит не тратить ресурсы ПК на хранение информации о тех узлах, которые обрабатывать не потребуется., в случае с поиском расстояния между двумя точками.
Рассмотрим его в деталях:
def Dijkstra(graph,start,end):
Сам алгоритм будет оформлен в качестве функции для удобства дальнейшего использования.
class NodeRecord:
node=None
connection=None
costSoFar=None
Создадим структуру данных, хранящую техническую информацию об узле графа в процессе обработки его алгоритмом Дейкстры. Она включает в себя идентификатор узла (его рабочее название), связь, через которую проходит кратчайший путь к этому узлу, а также стоимость такого пути и суммарный вес всех рёбер в его составе.
startRecord =NodeRecord()
startRecord.node = start
startRecord.connection = None
startRecord.costSoFar = 0
Инициализируем начальный узел.
olist= [startRecord]
clist = []
Далее алгоритм будет работать с 2 списками (массивами) узлов (NodeRecord):
- Открытый список (olist) – множество доступных (полученных через связи от проверенных), но непроверенных узлов.
- Закрытый список (clist) – множество проверенных узлов.
Алгоритм будет обрабатывать узлы открытого списка до тех пор, пока они остались, т.е. пока в графе есть непроверенные доступные узлы.
while len(olist) > 0:
tlist=[i.costSoFar for i in olist]
current=olist[tlist.index(min(tlist))]
На каждой итерации обрабатывается узел из открытого списка. Для равномерности выбирается узел наименее удалённый от начала.
if current.node == end:
break
Поскольку мы рассматриваем узлы в порядке отдаления от начала, первый же случай нахождения конца пути позволит сразу сгенерировать верный путь до него, поэтому при нахождении конца пути стоит выйти из цикла обработки графа.
connections = graph[current.node]
for connection in connections:
endNode = connection
endNodeCost = current.costSoFar + graph[current.node][connection]
Далее алгоритм проходит по связям, исходящим из данного узла.
if endNode in [clist[ite].node for ite in range(len(clist))]:
endNodeRecord = clist[[clist[ite].node for ite in range(len(clist))].index(endNode)]
if endNodeRecord.costSoFar <= endNodeCost:
continue
clist.pop(clist.index(endNodeRecord))
Если связь ведёт к узлу закрытого списка, то проверяется, не является ли маршрут к этому узлу через выбранную связь короче, чем уже полученный для него. Если это так, то запись об этом узле будет обновлена, иначе цикл переходит к следующей итерации.
elif endNode in [olist[ite].node for ite in range(len(olist))]:
endNodeRecord = olist[[olist[ite].node for ite in range(len(olist))].index(endNode)]
if endNodeRecord.costSoFar <= endNodeCost:
continue
Аналогично с открытым списком, но обновление информации об узле происходит проще.
else:
endNodeRecord = NodeRecord()
endNodeRecord.node = endNode
endNodeRecord.costSoFar = endNodeCost
endNodeRecord.connection = current
if not endNodeRecord in olist :
olist.append(endNodeRecord)
Если узел, к которому ведёт данная связь отсутствует в обоих списках, то он добавляется в открытый список по данным от этой связи.
clist.append(current)
olist.pop(olist.index(current))
Завершающая часть обработки узла – он переходит из открытого списка закрытый.
else:
return -1
Оператор else для цикла while срабатывает, если цикл был завершён из-за нарушения условия, таким образом если мы в процессе обработки обнаружили конец пути, цикл завершится через break и в действия описанные после elseне выполняются. В противном же случае мы не нашли конец пути, значит следует вернуть значение -1 вместо пути.
path = [end]
while current.node!=start:
current=current.connection
path.insert(0,current.node)
return path
Наконец, если путь был найден, происходит генерация пути по закрытому списку. Берётся узел конца пути, перед ним в путь вставляется узел, из которого к нему ведёт оптимальный путь от начала согласно алгоритму Дейкстры, аналогичное повторяется до тех пор, пока не будет достигнут узел начала пути. Полученная последовательность – искомый путь.
Примеры использования данного алгоритма на обычном взвешенном графе, который мы рассмотрели ранее:
>>> graph={
'A': {'B': 2, 'D': 4},
'C': {'B': 4, 'F': 2},
'B': {'A': 2, 'C': 4, 'D': 3},
'E': {'D': 9, 'F': 3},
'D': {'A': 4, 'B': 3, 'E': 9},
'F': {'C': 2, 'E': 3}}
>>> print Dijkstra(graph,'A','E')
['A', 'B', 'C', 'F', 'E']
>>> print Dijkstra(graph,'D','C')
['D', 'B', 'C']
>>> print Dijkstra(graph,'E','A')
['E', 'F', 'C', 'B', 'A']
>>> graph2={
'A': {'B': 2, 'D': 4},
'C': {'B': 4, 'F': 2},
'B': {'A': 2, 'C': 4, 'D': 3},
'E': {'D': 9, 'F': 3},
'D': {'A': 4, 'B': 3, 'E': 9},
'F': {'E': 3}}
print Dijkstra(graph2,'A','E')
['A', 'B', 'C', 'F', 'E']
>>> print Dijkstra(graph2,'E','A')
['E', 'D', 'A']
Теперь изменим описание алгоритма Дейкстры для поиска пути из заданной точки до всех точек графа:
def Dijkstra2(graph,start):
class NodeRecord:
node=None
connection=None
costSoFar=None
startRecord =NodeRecord()
startRecord.node = start
startRecord.connection = None
startRecord.costSoFar = 0
olist= [startRecord]
clist = []
while len(olist) > 0:
current=olist[0]
connections = graph[current.node]
for connection in connections:
endNode = connection
endNodeCost = current.costSoFar + graph[current.node][connection]
if endNode in [clist[ite].node for ite in range(len(clist))]:
endNodeRecord = clist[[clist[ite].node for ite in range(len(clist))].index(endNode)]
if endNodeRecord.costSoFar <= endNodeCost:
continue
clist.pop(clist.index(endNodeRecord))
elif endNode in [olist[ite].node for ite in range(len(olist))]:
endNodeRecord = olist[[olist[ite].node for ite in range(len(olist))].index(endNode)]
if endNodeRecord.costSoFar <= endNodeCost:
continue
else:
endNodeRecord = NodeRecord()
endNodeRecord.node = endNode
endNodeRecord.costSoFar = endNodeCost
endNodeRecord.connection = current
if not endNodeRecord in olist :
olist.append(endNodeRecord)
clist.append(current)
olist.pop(olist.index(current))
paths=[]
for end in clist:
if end.node==start:continue
current=end
path = [end.node]
while current.node!=start:
current=current.connection
path.insert(0,current.node)
path.insert(0,start+':'+end.node)
paths.append(path)
return paths
Вместо пошагового объяснения описания алгоритма будет разумнее просто перечислить отличия от исходного:
Алгоритм теперь не требует узла конца пути, поскольку в роли конца пути будет выступать каждая вершина графа кроме начальной.
Теперь обработка графа всегда идёт до тех пор, пока есть необработанные доступные элементы. Алгоритм не предусматривает выход при достижении какого-либо узла.
Теперь генерация пути идёт по очереди для всех элементов графа кроме начальной точки поиска пути.
Примеры использования данного алгоритма:
>>> graph={
'A': {'B': 2, 'D': 4},
'C': {'B': 4, 'F': 2},
'B': {'A': 2, 'C': 4, 'D': 3},
'E': {'D': 9, 'F': 3},
'D': {'A': 4, 'B': 3, 'E': 9},
'F': {'C': 2, 'E': 3}}
>>> print Dijkstra2(graph,'A')
[['A:B', 'A', 'B'], ['A:D', 'A', 'D'], ['A:C', 'A', 'B', 'C'], ['A:F', 'A', 'B', 'C', 'F'], ['A:E', 'A', 'B', 'C', 'F', 'E']]
print Dijkstra2(graph,'D')
[['D:B', 'D', 'B'], ['D:A', 'D', 'A'], ['D:C', 'D', 'B', 'C'], ['D:E', 'D', 'E'], ['D:F', 'D', 'B', 'C', 'F']]
В данном случае, в неориентированном графе (graph), кратчайший путь от узлаEдоAпроходит через связьF-C, а поскольку во втором случае (graph2) она актуальна только из вершиныCвF, алгоритм выдаёт более длинный путь через связьE-D.