Ускорение алгоритма Дейкстры

Question

У меня есть алгоритм Дейкстры:

   # ==========================================================================
# We will create a dictionary to represent the graph
# =============================================================================
graph = {
    'a' : {'b':3,'c':4, 'd':7},
    'b' : {'c':1,'f':5},
    'c' : {'f':6,'d':2},
    'd' : {'e':3, 'g':6},
    'e' : {'g':3, 'h':4},
    'f' : {'e':1, 'h':8},
    'g' : {'h':2},
    'h' : {'g':2}
}

def dijkstra(graph, start, goal):
    shortest_distance = {}     # dictionary to record the cost to reach to node. We will constantly update this dictionary as we move along the graph.
    track_predecessor = {}     # dictionary to keep track of path that led to that node.
    unseenNodes = graph.copy() # to iterate through all nodes
    infinity = 99999999999     # infinity can be considered a very large number
    track_path = []            # dictionary to record as we trace back our journey

    # Initially we want to assign 0 as the cost to reach to source node and infinity as cost to all other nodes
    for node in unseenNodes:
        shortest_distance[node] = infinity
    shortest_distance[start] = 0

    # The loop will keep running until we have entirely exhausted the graph, until we have seen all the nodes
    # To iterate through the graph, we need to determine the min_distance_node every time.
    while unseenNodes:
        min_distance_node = None
        for node in unseenNodes:
            if min_distance_node is None:
                min_distance_node = node
            elif shortest_distance[node] < shortest_distance[min_distance_node]:
                min_distance_node = node

        # From the minimum node, what are our possible paths
        path_options = graph[min_distance_node].items()

        # We have to calculate the cost each time for each path we take and only update it if it is lower than the existing cost
        for child_node, weight in path_options:
            if weight + shortest_distance[min_distance_node] < shortest_distance[child_node]:
                shortest_distance[child_node] = weight + shortest_distance[min_distance_node]
                track_predecessor[child_node] = min_distance_node

        # We want to pop out the nodes that we have just visited so that we dont iterate over them again.
        unseenNodes.pop(min_distance_node)

    # Once we have reached the destination node, we want trace back our path and calculate the total accumulated cost.
    currentNode = goal
    while currentNode != start:
        try:
            track_path.insert(0, currentNode)
            currentNode = track_predecessor[currentNode]
        except KeyError:
            print('Path not reachable')
            break
    track_path.insert(0, start)

    #  If the cost is infinity, the node had not been reached.
    if shortest_distance[goal] != infinity:
        print('Shortest distance is ' + str(shortest_distance[goal]))
        print('And the path is ' + str(track_path))

Это прекрасно работает, если у меня небольшое количество узлов (как в коде), но у меня есть граф с 480 000 узлами и, по моим приблизительным подсчетам, это найдет в таком большом пути массива за 7,5 часов, и это только 1 путь! Как я мог заставить это работать быстрее? В OSM, например, он рассчитывает в секундах!

Answer 1

Основная проблема, похоже, заключается в использовании unseenNodes. На каждой итерации вы ищете node, минимизирующий shortest_distance[node], перебирая все узлы в unseenNodes, что занимает время O (V). Это делается изнутри al oop, который повторяет V раз, поэтому общая сложность равна O (V² + E), где член E относится к другому l oop над path_options, который считает каждое ребро не более чем постоянным количество раз.

Более эффективно использовать очередь приоритетов структуру данных, такую ​​как heap , чтобы выполнить операцию «найти и удалить минимум» в меньше, чем O (V) время. Обратите внимание, что вам нужно вставить узел в очередь с приоритетами, только если у вас есть путь к нему. Псевдокод для реализации алгоритма Дейкстры с использованием очереди приоритетов можно найти в Wikipedia .

Answer 2

Обычно такие вещи можно улучшить с помощью numba. Я сделал быстрый пример того, как вы могли бы реализовать это. В pycharm он выводит много лишних вещей, но это не так уж и важно.

Способ работает так, что вместо того, чтобы читать все построчно, numba компилирует ваш код. Для коротких программ это увеличивает время выполнения на пару секунд. Тем не менее, вы говорите о нескольких часах, так что это определенно сделает ваш код быстрее.

# ==========================================================================
# We will create a dictionary to represent the graph
# =============================================================================
from numba import jit

graph = {
    'a' : {'b':3,'c':4, 'd':7},
    'b' : {'c':1,'f':5},
    'c' : {'f':6,'d':2},
    'd' : {'e':3, 'g':6},
    'e' : {'g':3, 'h':4},
    'f' : {'e':1, 'h':8},
    'g' : {'h':2},
    'h' : {'g':2}
}

@jit
def _dijkstra(graph, start, goal):
    shortest_distance = {}     # dictionary to record the cost to reach to node. We will constantly update this dictionary as we move along the graph.
    track_predecessor = {}     # dictionary to keep track of path that led to that node.
    unseenNodes = graph.copy() # to iterate through all nodes
    infinity = 99999999999     # infinity can be considered a very large number
    track_path = []            # dictionary to record as we trace back our journey

    # Initially we want to assign 0 as the cost to reach to source node and infinity as cost to all other nodes
    for node in unseenNodes:
        if node in shortest_distance:
            del shortest_distance[node]
        shortest_distance[node] = infinity
    del shortest_distance[start]
    shortest_distance[start] = 0

    # The loop will keep running until we have entirely exhausted the graph, until we have seen all the nodes
    # To iterate through the graph, we need to determine the min_distance_node every time.
    while unseenNodes:
        min_distance_node = None
        for node in unseenNodes:
            if min_distance_node is None:
                min_distance_node = node
            elif shortest_distance[node] < shortest_distance[min_distance_node]:
                min_distance_node = node

        # From the minimum node, what are our possible paths
        path_options = graph[min_distance_node].items()

        # We have to calculate the cost each time for each path we take and only update it if it is lower than the existing cost
        for child_node, weight in path_options:
            if weight + shortest_distance[min_distance_node] < shortest_distance[child_node]:
                if child_node in shortest_distance:
                    del shortest_distance[child_node]
                if child_node in track_predecessor:
                    del track_predecessor[child_node]
                shortest_distance[child_node] = weight + shortest_distance[min_distance_node]
                track_predecessor[child_node] = min_distance_node

        # We want to pop out the nodes that we have just visited so that we dont iterate over them again.
        unseenNodes.pop(min_distance_node)

    return track_path, track_predecessor, shortest_distance, infinity

def dijkstra(graph, start, goal):
    track_path, track_predecessor, shortest_distance, infinity = _dijkstra(graph, start, goal)

    # Once we have reached the destination node, we want trace back our path and calculate the total accumulated cost.
    currentNode = goal
    while currentNode != start:
        try:
            track_path.insert(0, currentNode)
            currentNode = track_predecessor[currentNode]
        except KeyError:
            print('Path not reachable')
            break
    track_path.insert(0, start)

    #  If the cost is infinity, the node had not been reached.
    if shortest_distance[goal] != infinity:
        print('Shortest distance is ' + str(shortest_distance[goal]))
        print('And the path is ' + str(track_path))

dijkstra(graph, 'a', 'h')

Причина, по которой я разделил его на dijkstra и _dijkstra, заключается в том, что я не смог получить numba составить вторую половину.