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

Question

我将我的C++实现转换Dijkstra's Algorithm为Java. 当我运行我的Java代码时，我没有得到预期的输出

C++从我的代码中预期：

Minimum distance for source vertex 0 to reach vertex 0 is 0

Minimum distance for source vertex 0 to reach vertex 1 is 4

Minimum distance for source vertex 0 to reach vertex 2 is 12

Minimum distance for source vertex 0 to reach vertex 3 is 19

Minimum distance for source vertex 0 to reach vertex 4 is 21

Minimum distance for source vertex 0 to reach vertex 5 is 11

Minimum distance for source vertex 0 to reach vertex 6 is 9

Minimum distance for source vertex 0 to reach vertex 7 is 8

Minimum distance for source vertex 0 to reach vertex 8 is 14

实际来自Java代码：

Minimum distance for source vertex 0 to reach vertex 0 is 0

Minimum distance for source vertex 0 to reach vertex 1 is 4

Minimum distance for source vertex 0 to reach vertex 2 is 2

Minimum distance for source vertex 0 to reach vertex 3 is 7

Minimum distance for source vertex 0 to reach vertex 4 is 9

Minimum distance for source vertex 0 to reach vertex 5 is 2

Minimum distance for source vertex 0 to reach vertex 6 is 1

Minimum distance for source vertex 0 to reach vertex 7 is 1

Minimum 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) {&nbsp; &nbsp;adj[i] = new ArrayList<>();}