인접행렬 구현

// N크기의 그래프 생성 & 초기화
graphs = new int[N + 1][N + 1];
for (int[] graph : graphs) {
    Arrays.fill(graph, Integer.MAX_VALUE);
}

// 거리 배열 생성 & 초기화
dis = new int[N + 1];
Arrays.fill(dis, Integer.MAX_VALUE);

// 방문 배열 생성
visit = new int[N + 1];

// 입력으로 그래프 초기값 대입(노드와 에지로 구성)
for (int i = 0; i < E; i++) {
    int v1 = sc.nextInt();
    int v2 = sc.nextInt();
    int w = sc.nextInt();
    graph[v1][v2] = w;
    graph[v2][v1] = w;
}

void dijkstra2() {
    // 시작 정점 초기화
    dis[1] = 0;
    visit[1] = 1;

    // 다익스트라 시작
    for (int i = 1; i <= N; i++) {
        // 비용이 가장 작은 인접 노드를 찾기 위한 변수 초기화
        int nextVertex = 1;
        int min = Integer.MAX_VALUE;

        // 시작 노드와 연결된 인접 노드 탐색(방문하지 않은 노드 중 최소 비용의 노드 탐색)
        for (int j = 1; j <= N; j++) {
            if (visit[nextVertex] == 0 && dis[nextVertex] < min) {
                min = dis[j];
                nextVertex = j;
            }
        }

        for(int k = 1; k <= N; k++) {
            if(visit[k] == 0 && (graph[nextVertex][k] != Integer.MAX_VALUE) ) { // 비용을 확인 가능하고 방문x 인접노드 중에서
                if(dis[k] > dis[nextVertex] + graph[nextVertex][k]) { //해당 노드를 거쳐가는게 빠르면
                    dis[k] = dis[nextVertex] + graph[nextVertex][k]; // 그 노드까지의 비용을 갱신함
                }
            }
        }
    }
}