无法理解 Dijkstra 的优先级队列实现
Trouble understanding Priority Queue implementation of Dijkstra
我在思考我们实现 Dijkstra 的逻辑流程到底是什么时遇到了一些麻烦，更准确地说，我遇到的问题是我们如何真正获取优先级队列，我们是否构建它（优先队列）当我们在图上执行算法时？还是我看错了？然后就是这样吗？我们是停在那里还是通过以某种其他形式将获得的信息放入优先级队列来进一步处理此输出，或者这是我们停止的地方？
我也理解为所选节点生成相应的最短路径的过程，通过递归地跟随我们首先形成最短路径的边，但它实际上是如何实现的？
总的来说，我有很多问题实际上能够想出 and/or 在学习期间理解算法的合适实现，我理解算法很好（在某些情况下我能够想出一个相近的替代品），但我就是想不出实施它们的巧妙方法，有什么建议吗？
我最好的建议是先从 bfs 开始。如果你能实现 BFS，你离 Dijkstra 只差一步。 BFS使用普通队列（先进先出），Dijkstra使用优先队列（根据当前到源节点的距离选择元素）。这是唯一的区别。
回答您的具体问题：
- 我们如何实际获取该优先级队列？您从一个空队列开始。在每次迭代中（Dijkstra 通常是迭代实现的，而不是递归实现的），您从队列中选择优先级最高的节点，并将该节点尚未访问过的所有邻居推回队列
- 我们在图上执行算法时是否构建它（优先级队列）？是的，在每次迭代中，您选择一个节点，然后推入多个节点到优先级队列
- 然后就是它了？是的，差不多就是它了。
- 次要细节：（1）您需要跟踪哪些节点已被挑选出来（并且永远不要将其推回）（2）可以将一个节点多次推入队列，并且它可以， (3) 需要一个trace数组来回溯到达节点的路径：每次push一个节点到队列中，记录该节点的trace为当前访问的节点（刚从队列中弹出）队列）
同样，从 BFS 开始，你会发现 Dijkstra 非常简单
我在思考我们实现 Dijkstra 的逻辑流程到底是什么时遇到了一些麻烦，更准确地说，我遇到的问题是我们如何真正获取优先级队列，我们是否构建它（优先队列）当我们在图上执行算法时？还是我看错了？然后就是这样吗？我们是停在那里还是通过以某种其他形式将获得的信息放入优先级队列来进一步处理此输出，或者这是我们停止的地方？
我也理解为所选节点生成相应的最短路径的过程，通过递归地跟随我们首先形成最短路径的边，但它实际上是如何实现的？
总的来说，我有很多问题实际上能够想出 and/or 在学习期间理解算法的合适实现，我理解算法很好（在某些情况下我能够想出一个相近的替代品），但我就是想不出实施它们的巧妙方法，有什么建议吗？
我最好的建议是先从 bfs 开始。如果你能实现 BFS，你离 Dijkstra 只差一步。 BFS使用普通队列（先进先出），Dijkstra使用优先队列（根据当前到源节点的距离选择元素）。这是唯一的区别。
回答您的具体问题：
- 我们如何实际获取该优先级队列？您从一个空队列开始。在每次迭代中（Dijkstra 通常是迭代实现的，而不是递归实现的），您从队列中选择优先级最高的节点，并将该节点尚未访问过的所有邻居推回队列
- 我们在图上执行算法时是否构建它（优先级队列）？是的，在每次迭代中，您选择一个节点，然后推入多个节点到优先级队列
- 然后就是它了？是的，差不多就是它了。
- 次要细节：（1）您需要跟踪哪些节点已被挑选出来（并且永远不要将其推回）（2）可以将一个节点多次推入队列，并且它可以， (3) 需要一个trace数组来回溯到达节点的路径：每次push一个节点到队列中，记录该节点的trace为当前访问的节点（刚从队列中弹出）队列）
同样，从 BFS 开始，你会发现 Dijkstra 非常简单