java - Java中的Dijkstra算法

Question

我在用 Java 实现 Dijkstra 算法时遇到了一些麻烦。
我使用这个(第一个)伪代码:http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
第 15 行，您需要获取距离最短的顶点。但是我怎样才能用相应的距离保存距离。
注意:顶点被定义为一个整数。

我的解决方案无法正常工作:

1. map K = 顶点，V = 距离，问题:长时间搜索以获得最小距离
2. K = 距离，V = 顶点的 SortedMap，问题:几乎每个距离都定义为 Integer.MAX_VALUE

所以我正在寻找一种将顶点保存到一定距离的快速方法，并且应该很容易获得具有最小距离的顶点。

Answer 1

尝试使用 PriorityQueue。这样，您就可以简单地移除头部，因为它的所有顶点距离最小。

在此处查看有关 PriorityQueue 的更多信息: http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html