难以理解Dijkstra的优先级队列实现

问题描述 投票:0回答:1

我在解决我们实现Dijkstra的逻辑流程到底是什么时遇到了麻烦,更确切地说,我遇到的问题是我们如何实际获取该优先级队列,我们​​如何构建它(优先级队列),因为我们打算在图形上执行算法?还是我看错了?然后是吗?我们是在这里停下来还是通过将获得的信息以其他某种形式放置在Priority Queue中来进一步处理此输出,还是在这里停下来?

我还理解了通过递归地遵循我们最初形成最短路径所采用的边来生成所选节点的相应最短路径的过程,但是实际上如何实现呢?]

[通常,我在学习期间实际上有很多问题能够思考和/或理解算法的合适实现,我对算法的理解很好(在某些情况下,我可以想到一个近似的替代方案),但我只是想不出实现它们的巧妙方法,有什么建议吗?

我在解决实现Dijkstra的逻辑流程到底是什么时遇到了麻烦,更确切地说,我遇到的问题是我们实际上如何获得优先级...

algorithm shortest-path
1个回答
0
投票
我最好的建议是先从bfs开始。如果您可以实施BFS,则距Dijkstra仅一步之遥。 BFS使用普通队列(先进先出),Dijkstra使用优先级队列(根据当前到源节点的距离选择元素)。那是唯一的区别。
© www.soinside.com 2019 - 2024. All rights reserved.