Dijkstra算法给出了错误的最短路径
Dijkstra Alogrithm gives wrong shortest path
我将 Dijkstra's Algorithm
的 C++
实现转换为 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++ 代码,我没有发现任何不同之处。
我已经花了很多时间调试我的代码。
我不明白哪里出了问题!我急需帮助,谢谢!
代码:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
public class Dijkstra
{
public static final int INF = 100000;
private static class IPair implements Comparable<IPair>
{
int first;
int second;
IPair(int first, int second)
{
this.first = first;
this.second = second;
}
public int compareTo(IPair that)
{
return this.first - that.first;
}
}
public static int[] dijkstra(List<IPair>[] adj, int source)
{
Queue<IPair> pq = new PriorityQueue<>();
int[] dist = new int[adj.length];
boolean[] visited = new boolean[adj.length];
Arrays.fill(dist, INF);
pq.add(new IPair(0, source));
dist[source] = 0;
while (!pq.isEmpty())
{
int u = pq.poll().second;
if (visited[u])
continue;
System.err.println(u);
visited[u] = true;
for (IPair pair : adj[u])
{
int v = pair.first;
int weight = pair.second;
if (dist[v] > dist[u] + weight)
{
dist[v] = dist[u] + weight;
pq.add(new IPair(dist[v], v));
System.err.println(Arrays.toString(dist));
}
}
}
return dist;
}
private static void addEdge(List<IPair>[] adj, int u, int v, int weight)
{
adj[u].add(new IPair(v, weight));
adj[v].add(new IPair(u, weight));
}
public static void main(String[] args)
{
int V = 9;
List<IPair>[] adj = new ArrayList[V];
Arrays.fill(adj, new ArrayList<IPair>());
addEdge(adj, 0, 1, 4);
addEdge(adj, 0, 7, 8);
addEdge(adj, 1, 2, 8);
addEdge(adj, 1, 7, 11);
addEdge(adj, 2, 3, 7);
addEdge(adj, 2, 8, 2);
addEdge(adj, 2, 5, 4);
addEdge(adj, 3, 4, 9);
addEdge(adj, 3, 5, 14);
addEdge(adj, 4, 5, 10);
addEdge(adj, 5, 6, 2);
addEdge(adj, 6, 7, 1);
addEdge(adj, 6, 8, 6);
addEdge(adj, 7, 8, 7);
int[] dist = dijkstra(adj, 0);
for (int i = 0; i < V; ++i)
System.out.println("Minimum distance for source vertex " + 0 + " to reach vertex " + i + " is " + dist[i]);
}
}
Arrays.fill(adj, new ArrayList<IPair>())
相当于:
List<IPair> list = new ArrayList<>();
Arrays.fill(adj, list)
这意味着您要在所有数组元素中存储 相同的 List
对象。当您更改 adj[x]
的 List
对象时,它会更改所有 adj
元素的 List
对象,因为它是同一个对象。
解决方案是在每个 adj
元素中存储一个新的 List
对象:
//Arrays.fill(adj, new ArrayList<IPair>());
for (int i = 0; i < V; ++i) {
adj[i] = new ArrayList<>();
}
我将 Dijkstra's Algorithm
的 C++
实现转换为 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++ 代码,我没有发现任何不同之处。
我已经花了很多时间调试我的代码。
我不明白哪里出了问题!我急需帮助,谢谢!
代码:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
public class Dijkstra
{
public static final int INF = 100000;
private static class IPair implements Comparable<IPair>
{
int first;
int second;
IPair(int first, int second)
{
this.first = first;
this.second = second;
}
public int compareTo(IPair that)
{
return this.first - that.first;
}
}
public static int[] dijkstra(List<IPair>[] adj, int source)
{
Queue<IPair> pq = new PriorityQueue<>();
int[] dist = new int[adj.length];
boolean[] visited = new boolean[adj.length];
Arrays.fill(dist, INF);
pq.add(new IPair(0, source));
dist[source] = 0;
while (!pq.isEmpty())
{
int u = pq.poll().second;
if (visited[u])
continue;
System.err.println(u);
visited[u] = true;
for (IPair pair : adj[u])
{
int v = pair.first;
int weight = pair.second;
if (dist[v] > dist[u] + weight)
{
dist[v] = dist[u] + weight;
pq.add(new IPair(dist[v], v));
System.err.println(Arrays.toString(dist));
}
}
}
return dist;
}
private static void addEdge(List<IPair>[] adj, int u, int v, int weight)
{
adj[u].add(new IPair(v, weight));
adj[v].add(new IPair(u, weight));
}
public static void main(String[] args)
{
int V = 9;
List<IPair>[] adj = new ArrayList[V];
Arrays.fill(adj, new ArrayList<IPair>());
addEdge(adj, 0, 1, 4);
addEdge(adj, 0, 7, 8);
addEdge(adj, 1, 2, 8);
addEdge(adj, 1, 7, 11);
addEdge(adj, 2, 3, 7);
addEdge(adj, 2, 8, 2);
addEdge(adj, 2, 5, 4);
addEdge(adj, 3, 4, 9);
addEdge(adj, 3, 5, 14);
addEdge(adj, 4, 5, 10);
addEdge(adj, 5, 6, 2);
addEdge(adj, 6, 7, 1);
addEdge(adj, 6, 8, 6);
addEdge(adj, 7, 8, 7);
int[] dist = dijkstra(adj, 0);
for (int i = 0; i < V; ++i)
System.out.println("Minimum distance for source vertex " + 0 + " to reach vertex " + i + " is " + dist[i]);
}
}
Arrays.fill(adj, new ArrayList<IPair>())
相当于:
List<IPair> list = new ArrayList<>();
Arrays.fill(adj, list)
这意味着您要在所有数组元素中存储 相同的 List
对象。当您更改 adj[x]
的 List
对象时,它会更改所有 adj
元素的 List
对象,因为它是同一个对象。
解决方案是在每个 adj
元素中存储一个新的 List
对象:
//Arrays.fill(adj, new ArrayList<IPair>());
for (int i = 0; i < V; ++i) {
adj[i] = new ArrayList<>();
}