Dijkstra 算法给出错误的最短路径

Question

我将我的C++实现转换Dijkstra's Algorithm为Java. 当我运行我的Java代码时，我没有得到预期的输出C++从我的代码中预期：Minimum distance for source vertex 0 to reach vertex 0 is 0Minimum distance for source vertex 0 to reach vertex 1 is 4Minimum distance for source vertex 0 to reach vertex 2 is 12Minimum distance for source vertex 0 to reach vertex 3 is 19Minimum distance for source vertex 0 to reach vertex 4 is 21Minimum distance for source vertex 0 to reach vertex 5 is 11Minimum distance for source vertex 0 to reach vertex 6 is 9Minimum distance for source vertex 0 to reach vertex 7 is 8Minimum distance for source vertex 0 to reach vertex 8 is 14实际来自Java代码：Minimum distance for source vertex 0 to reach vertex 0 is 0Minimum distance for source vertex 0 to reach vertex 1 is 4Minimum distance for source vertex 0 to reach vertex 2 is 2Minimum distance for source vertex 0 to reach vertex 3 is 7Minimum distance for source vertex 0 to reach vertex 4 is 9Minimum distance for source vertex 0 to reach vertex 5 is 2Minimum distance for source vertex 0 to reach vertex 6 is 1Minimum distance for source vertex 0 to reach vertex 7 is 1Minimum distance for source vertex 0 to reach vertex 8 is 2我试图在我的 Java 代码中寻找一个错误，我仔细检查了我是否正确复制了我的 C++ 代码，我没有发现任何不同之处。我已经花了很多时间调试我的代码。我不明白出了什么问题！我急需帮助，谢谢！

Answer 1

Arrays.fill(adj, new ArrayList<IPair>())

相当于：

List<IPair> list = new ArrayList<>();

Arrays.fill(adj, list)

这意味着您在所有数组元素中存储相同的对象。 List当您更改 的List对象时adj[x]，它会更改List所有adj元素的对象，因为它是同一个对象。解决方案是在每个元素

中存储一个新对象：Listadj

//Arrays.fill(adj, new ArrayList<IPair>());

for (int i = 0; i < V; ++i) {

   adj[i] = new ArrayList<>();

}