public void Dijkstra {
    int V;                 // 정점 개수
    int[][] adjMatrix;     // 인접한 정점 간 가중치 저장한 배열
    int[] distance;        // start 에서 자신으로 오는 최소 비용, S~v (다른 정점을 여러개 거칠 수도, 아닐 수도 있음)
    boolean[] visited;     // 경유지로 고려해본 정점인지를 저장
    int start, end;        // 시작정점과 도착정점

    distance[start] = 0;   // 출발지에서 출발지까지 거리 0으로 초기화

    // 정점 개수만큼 반복하며 정점 별 최단거리 채워감
    for (int i=0; i<V; i++) {
        // 1) 아직 방문하지 않은 정점 중, 출발지로부터 가장 가까운 정점을 경유지로 선택
        int min = Integer.MAX_VALUE;
        int stopOver = 0;

        for (int j=0; j<V; j++) {
            if (!visited[j] && distance[j] < min) {     // distance 배열의 최솟값을 찾기
                min = distance[j];
                stopOver = j;         // 경유지로 선택
            }
        }
        visited[stopOver] = true;

        // 2) 위에서 선택된 경유지의 인접한 정점 중, 해당 경유지를 거쳐서 가면 더 최단으로 갈 수 있는 경로의 거리를 업데이트
        for (int j=0; j<V; j++) {
            if (!visited[j] && min+adjMatrix[stopOver][j] != 0 && min+adjMatrix[stopOver][j] < distance[j]) {      // 아직 방문하지 않고, 경유지와 인접하며, 경유지를 거쳐가면 더 빨리 도착할 수 있으면
                distance[j] = min+adjMatrix[stopOver][j];     // 최단 경로 갱신
            }
        }
    }
    System.out.println(distance[end]);        // 최종 도착지까지의 최단 경로 출력
}

public class Dijkstra_PQ {
    class Vertex implements Comparable {
        int no, distance;

        public Vertex(int no, int distance) {
			super();
			this.no = no;
			this.distance = distance;
		}

		@Override
		public int compareTo(Vertex o) {
			return this.distance - o.distance;
		}
    }

    public void Dijkstra {
    int V;                 // 정점 개수
    int[][] adjMatrix;     // 인접한 정점 간 가중치 저장한 배열
    int distance;          // start 에서 자신으로 오는 최소 비용, S~v (다른 정점을 여러개 거칠 수도, 아닐 수도 있음)
    boolean[] visited;     // 경유지로 고려해본 정점인지를 저장
    int start, end;        // 시작정점과 도착정점

    distance[start] = 0;   // 출발지에서 출발지까지 거리 0으로 초기화
    PriorityQueue<Vertex> pq = newPriorityQueue<>();
    pq.offer(new Vertex(start, distance[start]));    // 최초에는 출발지를 큐에 삽입

    while(!pq.isEmpty()) {
        // 1) 아직 방문하지 않은 정점 중, 출발지로부터 가장 가까운 정점을 경유지로 선택
        Vertex stopOver = pq.poll();           // 우선순위 큐 덕분에 자동적으로 최단 거리 정점 구함

        if (visited[stopOver.no]) continue;    // 단, 방문했으면 pass

        visited[stopOver.no] = true;

        if (stopOver.no == end) break;         // 도착지에 도착하면 탈출

        // 2) 위에서 선택된 경유지의 인접한 정점 중, 해당 경유지를 거쳐서 가면 더 최단으로 갈 수 있는 경로의 거리를 업데이트
        for (int j=0; j<V; k++) {
            if (!visited[j] && adjMatrix[stopOver.no][j] && stopOver.distance+adjMatrix[stopOver.no][j] < distance[j]) {     // 아직 방문하지 않고, 경유지와 인접하며, 경유지를 거쳐가면 더 빨리 도착할 수 있으면
                distance[j] = stopOver.distance + adjMatrix[stopOver.no][j];     // 출발지에서부터 경유지까지의 거리와 경유지로부터 인접한 정점까지의 거리를 더한 값(경유 비용)으로 최단 거리 갱신
                pq.offer(new Vertex(j, distance[j]));      // 업데이트 된 최단거리는 큐에 삽입
            }
        }
    }
    System.out.println(distance[end]);        // 최종 도착지까지의 최단 경로 출력
}