0
我正在嘗試使用鄰接列表和優先級隊列來實現Dijkstra算法，但是獲得某些頂點的錯誤輸出。由於Java中內置優先級隊列中沒有reduceKey方法，因此我添加了新的頂點（距離源的更新距離）。任何人都可以提出我錯在哪裏？我的代碼是：Dijkstra執行中的輸出不正確
class Graph3 {
private int V;
private ArrayList<Integer> adj [];
Map<String, Integer> weight; //for O(1) lookup of edge weight
PriorityQueue<Vertex> minHeap;
int d [];
int p[];
boolean visited [];
Graph3(int n) {
this.V = n;
adj = new ArrayList[n];
for(int i=0; i<n; i++) {
adj[i] = new ArrayList<Integer>();
}
weight = new HashMap<String, Integer>();
minHeap = new PriorityQueue<Vertex>(n, new Vertex());
visited = new boolean[n];
Arrays.fill(visited, false);
p = new int[n];
Arrays.fill(p, -1);
d = new int[n];
Arrays.fill(d,Integer.MAX_VALUE);
}
public void addEdge(int a, int b, int w) {
adj[a].add(b);
weight.put(a+","+b,w); //cost of edge(a,b)
}
public void calculateShortest(int source) {
d[source] = 0;
visited[source] = true;
for(int i=0; i<V; i++) minHeap.offer(new Vertex(i,d[i]));
while(!minHeap.isEmpty()) {
Vertex u = minHeap.poll();
relaxEdges(u); //relax all outgoing edges of u
}
for(int i=0; i<d.length; i++) {
System.out.println("Shortest path from "+source+" to vertex "+i+" = "+d[i]);
}
}
public void relaxEdges(Vertex u) {
for(int i: adj[u.getName()]) {
if(!visited[i]) {
int alt = d[u.getName()] + weight.get(u.getName()+","+i);
if(d[i] > alt) {
d[i] = alt;
Vertex temp = new Vertex(i,d[i]);
minHeap.offer(temp);
p[i] = u.getName();
visited[i] = true;
}
}
}
}
}
//to be used for binding every vertex with dval for use in PQ
class Vertex implements Comparator<Vertex> {
int name;
int dval; //current min distance from source
public Vertex() {
}
public Vertex(int name, int dval) {
this.name = name;
this.dval = dval;
}
public int getName() {
return name;
}
public void setName(int name) {
this.name = name;
}
public int getDval() {
return dval;
}
public void setDval(int dval) {
this.dval = dval;
}
public int compare(Vertex a, Vertex b) {
return (a.dval - b.dval);
}
}
public class DijkstraShortestPath {
public static void main(String args []) {
Graph3 g = new Graph3(9);
g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);
g.calculateShortest(0);
}
}
**My Output :**
Shortest path from 0 to vertex 0 = 0
Shortest path from 0 to vertex 1 = 4
Shortest path from 0 to vertex 2 = 12
Shortest path from 0 to vertex 3 = 19
Shortest path from 0 to vertex 4 = 28
Shortest path from 0 to vertex 5 = 16
Shortest path from 0 to vertex 6 = 18
Shortest path from 0 to vertex 7 = 8
Shortest path from 0 to vertex 8 = 15
**Correct Output :**
Shortest path from 0 to vertex 0 = 0
Shortest path from 0 to vertex 1 = 4
Shortest path from 0 to vertex 2 = 12
Shortest path from 0 to vertex 3 = 19
Shortest path from 0 to vertex 4 = 21
Shortest path from 0 to vertex 5 = 11
Shortest path from 0 to vertex 6 = 9
Shortest path from 0 to vertex 7 = 8
Shortest path from 0 to vertex 8 = 14