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

我将我的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++ 代码,我没有发现任何不同之处。


我已经花了很多时间调试我的代码。


我不明白出了什么问题!我急需帮助,谢谢!


动漫人物
浏览 93回答 1
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<>();}
打开App,查看更多内容
随时随地看视频慕课网APP

相关分类

Java