加速Dijkstra算法

Question

我有Dijkstra algyrithm：

   # ==========================================================================
# 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))

如果我有少量的节点(就像在代码中)，它工作得很好，但我有大约48万个节点的图，根据我的近似计算，它将在7.5小时内在如此大的数组路径中找到，这只是一种方式！我怎么才能让它工作得更快呢？例如，在OSM中，它以秒为单位进行计算！

Answer 1

通常，这类事情可以通过使用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编译后半部分。

Answer 2

主要的问题似乎是您对unseenNodes的使用。在每次迭代中，通过迭代unseenNodes中的所有节点来搜索node最小化shortest_distance[node]，这需要O(V)时间。这是从循环内部完成的，循环迭代V次，因此总体复杂度为O(V²+ E)，其中E项表示path_options上的另一个循环，该循环最多将每条边视为恒定次数。

使用诸如heap之类的priority queue数据结构以便在少于O(V)时间内执行“查找和删除最小值”操作是更有效的。请注意，只有在有了指向节点的路径后，才需要将该节点插入到优先级队列中。使用优先级队列实现Dijkstra算法的伪代码可以在Wikipedia上找到。