我的 djikstra 算法实现有什么问题。它没有通过所有测试用例吗？

Question

我正在努力用 Java 实现 Dijkstra 算法来查找图中的最短路径。虽然我编写了下面的代码，但我遇到了其功能问题。这是代码：

import java.util.*;
class Graph{
    Map<Integer,List<Edge>>adjacencyList;

    public Graph(){
adjacencyList=new HashMap<>();
    }
    public void addEdge(int source,int destination,int weight){
        adjacencyList.putIfAbsent(source,new ArrayList<>());
        adjacencyList.putIfAbsent(destination,new ArrayList<>());
        adjacencyList.get(source).add(new Edge(destination,weight));
adjacencyList.get(destination).add(new Edge(source,weight));
    }

    public Map<Integer,Integer> dij(int start){

        PriorityQueue<Edge> pq=new PriorityQueue<>(Comparator.comparingInt(edge->edge.weight));
        Map<Integer,Integer> distances=new HashMap<>();

        for(Integer node: adjacencyList.keySet()){
distances.put(node,Integer.MAX_VALUE);
        }
        distances.put(start,0);
        pq.add(new Edge(start, 0));

while(!pq.isEmpty()){

    Edge curr=pq.poll();
 int curnode=curr.node;
 int currDist=curr.weight;

for( Edge neighbour:adjacencyList.getOrDefault(curnode, new ArrayList<>()) ){

    int newDist=distances.get(curnode)+neighbour.weight;
if (currDist > distances.get(curnode)) {
    continue;
}

    if(newDist<distances.get(neighbour.node)){
 distances.put(neighbour.node, newDist);
 pq.add(new Edge(neighbour.node, newDist));
    }


}




}
return distances; 
    }
}

class Edge{
    int node;
    int weight;

    
        public Edge(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
}

       
        
    

public class Solution {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in); 
        int V = s.nextInt();
        int E = s.nextInt();
        Graph graph=new Graph();
        for(int i=0;i<E;i++){
            int ei=s.nextInt();
            int ej=s.nextInt();
            int w=s.nextInt();
 graph.addEdge(ei, ej, w);
        }
int start=0;

Map<Integer,Integer> ans=graph.dij(start);

for(Map.Entry entry:ans.entrySet()){
    System.out.println(entry.getKey()+" "+entry.getValue());
}

        }

        
    }

在此实现中，我希望计算从指定起始节点到图中所有其他节点的最短距离。但是，当我运行代码时，我没有得到预期的结果 需要你的帮助

Answer 1

问题在于

dij

方法中的以下代码行。

if (currDist > distances.get(curnode)) {
    continue;
}

如果你考虑 for

curNode = start

，对于上面语句的每个邻居都是 true，所以后面的代码永远不会被执行[在论文中尝试这种情况]。所以你的最终 dij 代码将是：

public Map<Integer, Integer> dij(int start) {
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(edge -> edge.weight));
        Map<Integer, Integer> distances = new HashMap<>();
        for (Integer node : adjacencyList.keySet()) {
            distances.put(node, Integer.MAX_VALUE);
        }
        distances.put(start, 0);
        pq.add(new Edge(start, 0));
        while (!pq.isEmpty()) {
            Edge curr = pq.poll();
            int curnode = curr.node;
            for (Edge neighbour : adjacencyList.getOrDefault(curnode, new ArrayList<>())) {
                int newDist = distances.get(curnode) + neighbour.weight;
                if (newDist < distances.get(neighbour.node)) {
                    distances.put(neighbour.node, newDist);
                    pq.add(new Edge(neighbour.node, newDist));
                }
            }
        }
        return distances;
    }

以上是使用以下测试用例进行测试的：
输入：

5 6
0 2 3
1 3 2
2 1 4
2 3 8
2 4 2
3 4 5

输出：

0 0
1 7
2 3
3 9
4 5