如何在存储在字典中的图形上启动 Dijkstra 算法

Question

我想实现 Dijkstra 的最短路径算法，我正在使用多级字典来表示我的图。例如：

g = {'A': {'C': 2}, 'B': {'B': 4, 'A': 2}}

我知道如何使用双 for 循环访问内部字典。但是，如果用户输入起点和终点，我会遇到使用此 for 循环在字典中搜索起点的问题：

start = input("Starting point : ")
for start in g:
    print start

这将改为打印里面的键，它总是从第一个键开始并遍历图表。和算法说的相反，就是把源点和其他所有节点比较，然后根据权值和其他所有节点比较之后的点，以此类推。

你能建议一个解决这个问题的方法吗？例如，如何从节点 B 而不是 A 开始而不是从第一个键开始？

另外，你推荐这种字典方法还是有更好的方法？

Answer 1

起始节点应该是您的 dijkstra 函数的参数。函数签名应该类似于 def dijkstra(graph, start):.

要遍历连接的节点，我会使用：

for node, cost in graph[start].items():
    print node, cost

同样在 dijkstra 中，您应该有一个数据结构来保存尚未探索的节点，这些节点按成本递减排序。通常使用优先级队列。

提示：dijkstra 函数内的主循环不会是 for 循环，而是 while 循环检查是否还有节点需要探索。

Answer 2

这段代码：

for start in g:
    print start

变量 start 遍历字典的每个键。如果你想在字典中打印对应于你的起点的value/subdictionary，只需使用

print g[start]

至于算法本身，Diego Allen 的建议是正确的。

Answer 3

Dijkstra算法解决了单源最短路径问题。给定一个图和图中的一个顶点，它找到到每个其他顶点的最短路径。

如果您希望实现运行快速，则必须使用 priority queue。最初使用字典表示图形很好，但您需要提取边并将它们插入优先级队列。回想一下，在 Dijkstra 算法的每次迭代中，您必须在跨越图中未探索部分和您已探索部分之间边界的所有边中选择成本最低的边。使用最小成本优先级队列，您可以在每次迭代中从队列中弹出成本最低的边。

优先级队列的一个简单有效的实现是 heap. I recommend that you either use Python's built-in heap queue 或使用列表实现您自己的最小堆。

如何在存储在字典中的图形上启动 Dijkstra 算法

How to start Dijkstra's algorithm on a graph stored in a dictionary

python

algorithm

dictionary

dijkstra

graph-algorithm