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

Далее пойдёт речь об алгоритме поиска расстояний между вершинами в графе. Он является обобщением фронтового алгоритма обхода. Единственное существенное отличие — вместо фронтового множества используется очередь с приоритетом.

Очередь с приоритетом

Очередь с приоритетом — абстрактный тип данных, эквивалентный следующему:

def make_pq(): return []

def pq_push(q,x,p): q.append((x,p))

def pq_pop(q): 
    priorities = [xp[1] for xp in q]
    min_index  = priorities.index(min(priorities))
    return q.pop(min_index)

def pq_is_empty(q): return len(q) == 0

Эффективную реализацию очереди с приоритетом отложим на потом, а сейчас приведём сам алгоритм Дейкстры.

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

Задача, которую решает алгоритм Дейкстры, следующая: дан взвешенный неотрицательными весами граф, нужно найти расстояние от заданной его вершины до всех остальных (или до какой-то определённой). Под расстоянием между вершинами понимается длина кратчайшего пути между ними. Длиной пути называется сумма весов вдоль этого пути.

Алгоритм Дейкстры почти полностью повторяет фронтовой алгоритм обхода, поэтому просто приведём код без лишних комментариев:

def traverse(graph, start):
    pq = make_pq(); pq_push(pq, start, 0)
    distances = {}
    while not pq_is_empty(pq):
        vertex, distance = pq_pop(pq)
        if vertex in distances: continue
        distances[vertex] = distance
        
        to_visit = [n for n in neighbors(graph,vertex)
                      if  n not in distances]
        
        for target in to_visit: 
            pq_push(pq, target, distance + graph[vertex][target])
            
    return distances