Алгоритм Дейкстры
Алгоритм Дейкстры - алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных.
Если поиск в ширину позволяет найти путь с минимальным количеством пересадок из точки А в точку В, то алгоритм Дейкстры позволяет найти самый быстрый путь из точки А в точку В.
Когда работаете с алгоритмом Дейкстры, с каждым ребром графа связывается число, называемое весом. Алгоритм Дейкстры работает с взвешенным графом и только с направленными ациклическими графами, которые нередко обозначаются сокращением DAG (Directed Acyclic Graph). Таким образом граф должен быть взвешенным, направленным и без циклов.
Граф с весами называется взвешенным графом.
Граф без весов называется невзвешенным графом.
Для вычисления кратчайшего пути в невзвешенном графе используется поиск в ширину. Кратчайшие пути во взвешенном графе вычисляются по алгоритму Дейкстры.
Использование алгоритма Дейкстры с графом содержащим ребра с отрицательным весом, невозможно. Для этих целей используется алгоритм Беллмана-Форда.
Алгоритм Дейкстры состоит из четырех шагов:
1. Найти узел с наименьшей стоимостью (т.е узел, до которого можно добраться за минимальное время)
2. Обновить стоимости соседей этого узла.
3. Повторять, пока это не будет сделано дл всех узлов графа.
4. Вычислить итоговый путь.
Посмотрим как это выглядит в коде. Например, у нас будет такой граф:
Для реализации этого примера нам нужны три хеш-таблицы (ассоциативные массивы или словари): для графа, для родителей и для стоимостей.
Для представления графа со стоимостью перехода к соседу мы можем воспользоваться хеш-таблицей в хеш-таблице или многомерным ассоциативным массивом.
graph = {}
graph['start'] = {}
graph['start']['a'] = 6
graph['start']['b'] = 2
graph['a'] = {}
graph['a']['end'] = 1
graph['b'] = {}
graph['b']['a'] = 3
graph['b']['end'] = 5
graph['end'] = {}
А для получения все соседей мы можем взять ключи:
print graph['start'].keys()
Хеш-таблицы для родителей и для хранения стоимостей:
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["end"] = infinity
parents = {}
parents['a'] = 'start'
parents['b'] = 'start'
parents['in'] = None
Массив для сохранения уже обработанных узлов:
processed = []Алгоритм выглядит следующим образом:
Код:
# graph
graph = {}
# start node
graph['start'] = {}
graph['start']['a'] = 6
graph['start']['b'] = 2
# node a
graph['a'] = {}
graph['a']['end'] = 1
# node b
graph['b'] = {}
graph['b']['a'] = 3
graph['b']['end'] = 5
# node end
graph['end'] = {}
# costs
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["end"] = infinity
#parents
parents = {}
parents['a'] = 'start'
parents['b'] = 'start'
parents['in'] = None
# for processed items
processed = []
# function to get lowest
def find_lowest_cost_node (costs):
lowest_cost = float("inf")
lowest_cost_node = None
for node in costs:
cost = costs[node]
if cost < lowest_cost and node not in processed:
lowest_cost = cost
lowest_cost_node = node
return lowest_cost_node
# main code
node = find_lowest_cost_node(costs)
while node is not None:
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys():
new_cost = cost + neighbors[n]
if costs[n] > new_cost:
costs[n] = new_cost
parents[n] = node
processed.append(node)
node = find_lowest_cost_node(costs)
# print parents
# print costs
