我有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))
如果我有少量节点（如代码中所示），效果很好，但是我有大约480 000个节点的图，根据我的近似计算，它将在7.5小时内找到这么大的数组路径，这仅是1路！我怎样才能使其更快地工作？例如，在OSM中，它以秒为单位进行计算！
通常，使用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来编译后半部分。