Dijkstra 알고리즘을 두 가지 방법으로 만든 Java 코드

1)집합을 이용하여 매번 최소 원소를 찾는 방식 : O(V^2)

double dijkstra1(){
    double[] distance = new double[vertexNum];
    HashSet<Integer> Q = new HashSet<>();
    Q.add(0);
    distance[0] = 0;
    for(int i=1; i<vertexNum; i++){
        Q.add(i);
        distance[i] = Double.MAX_VALUE;
    }
    while(!Q.isEmpty()){
        Iterator<Integer> itr = Q.iterator();
        int minVertex = 0;
        double minWeight = Double.MAX_VALUE;
        //아직 가지 않은 vertex 중 최소 찾기
        while(itr.hasNext()){
            int v = itr.next();
            if(distance[v] < minWeight){
                minVertex = v;
                minWeight = distance[v];
            }
        }
        Q.remove(minVertex);
        for(int i : graph.get(minVertex).keySet()){
            if(Q.contains(i) && distance[i] > distance[minVertex] + graph.get(minVertex).get(i)){
                distance[i] = distance[minVertex] + graph.get(minVertex).get(i);
            }
        }
    }
    return distance[vertexNum - 1];
}

2)우선순위 큐를 이용하는 방식 : O(E + V*logV)

//우선순위 큐에 넣을 (도착지, 가중치) 쌍 클래스
class Pair implements Comparable<Pair>{
    int vertex;
    double distance;
    
    Pair(int v, double d){
        vertex = v;
        distance = d;
    }
 
    @Override
    public int compareTo(Pair o) {
        return (int) (distance - o.distance);
    }
}
 
double dijkstra2(){
    double[] distance = new double[vertexNum];
    distance[0] = 0;
    for(int i=1; i<vertexNum; i++) distance[i] = Double.MAX_VALUE;
    PriorityQueue<Pair> heap = new PriorityQueue<>();
    heap.add(new Pair(0, distance[0]));
    while(!heap.isEmpty()){
        Pair p = heap.poll();
        if(distance[p.vertex] < p.distance) continue;
        for(int i : graph.get(p.vertex).keySet()){
            if(distance[i] > distance[p.vertex] + graph.get(p.vertex).get(i)){
                distance[i] = distance[p.vertex] + graph.get(p.vertex).get(i);
                heap.add(new Pair(i, distance[i]));
            }
        }
    }
    return distance[vertexNum - 1];
}