프림, 다익스트라 알고리즘에 대하여.java

프림 알고리즘과 다익스트라 알고리즘의 공통점

 

• 그래프 최소 비용의 관점에서, 최소 비용을 탐색한다는 것이 가장 큰 공통점
• 구현 방법에서 반복문과 우선순위 큐 모두 사용 가능

 

 

 

 

 

프림 알고리즘과 다익스트라 알고리즘의 차이점

 

	프림 알고리즘	다익스트라 알고리즘
간선 선택 기준	선택한 정점과 인접한 정점들 중 최소비용의 간선이 존재하는 정점 선택	해당 노드로 향하는 경로의 최소값, 간선의 가중치의 합이 최소인 경로
시작 노드의 차이에 따른 결과값 변화	없음 (모든 정점에 대해 동일한 결과)	있음 (정점마다 결과값이 달라짐)
저장 핵심 데이터	간선의 가중치	해당 정점에 도달하기 위한 최소 cost 저장 (경로를 포함)

 

 

🖥️코드 구현

 

import java.util.*;

public class 다익스트라_우선순위큐 {

    static class Node implements Comparable<Node> {
        int v, w;

        public Node(int v, int w) {
            this.v = v;
            this.w = w;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.w, o.w);
        }
    }

    static final int INF = 987654321;
    static int V,E;
    static List<Node>[] adjList; //인접리스트
    static int[] dist;


    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        V = sc.nextInt();
        E = sc.nextInt();

        adjList = new ArrayList[V];
        for(int i = 0 ; i<V; i++){
            adjList[i] = new ArrayList<>();
        } //초기화 완료


        dist = new int[V];
        Arrays.fill(dist,INF);

        for(int i = 0; i<E; i++){
            //시작정점 도착정점 가중치 순으로 입력이 된다.
            adjList[sc.nextInt()].add(new Node(sc.nextInt(),sc.nextInt()));
        }

        dijsktra(0);

        System.out.println(Arrays.toString(dist));



    }

    private static void dijsktra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();

        boolean[] visited = new boolean[V]; //방문처리
        dist[start] = 0; //시작노드까지의 거리는 0으로 초기화

        pq.add(new Node(start,0));

        while (!pq.isEmpty()){
            Node curr = pq.poll();

            if(visited[curr.v]) continue; //이미 방문했다면 비용을 알고 있다는 뜻!
                visited[curr.v] =true; //선택

            for(Node node: adjList[curr.v]) {
                if (!visited[node.v] && dist[node.v] > dist[curr.v] + node.w) {
                    dist[node.v] = dist[curr.v] + node.w;
                    pq.add(new Node(node.v, dist[node.v]));
                }
            }
        }

    }
}

 

import java.util.Arrays;
import java.util.Scanner;

public class 프림_반복문 {

    static final int INF = Integer.MAX_VALUE;
    //987654321

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int V = sc.nextInt(); //0부터 시작
        int E = sc.nextInt();



        //인정행렬
        int[][] adjArr = new int[V][V];

        for(int i= 0 ; i<E; i++){
            int A = sc.nextInt();
            int B = sc.nextInt();
            int W = sc.nextInt();
            //무향 그래프
            adjArr[A][B] = adjArr[B][A] = W;
        }//입력끝

        //방문처리를 위해 배열 선언
        boolean[] visited = new boolean[V]; //이거 골랐어!
        int[] p = new int[V]; // 내가 어디서 왔는지 이거 문제에 따라서 필요할 수 도 있고, 아닐수도
        int[] dist = new int[V]; //key 라고 했던 가장 작은 비용을 저장하기 위한 배열
        //2차원 배열로도 가능하긴 하다

        //dist 초기화
        for(int i = 0 ; i<V; i++) {
            dist[i] = INF;
//            p[i] = -1;
        }
//        Arrays.fill(dist,INF); 

        //임의의 한점을 선택해서 돌려야한다
        dist[0] = 0; //0번 정점부터 할래요
        int ans = 0 ;

        for(int i = 0; i< V; i++ ) { //V로 쓰든 V-1로 쓰든 상관이 읎다!
            int min = INF;
            int idx = -1;
            //아직 안뽑힌 정점들 중 가장 작은 값을 뽑겟다.
            for(int j =0 ; j<V ; j++){
                if(!visited[j] && dist[j] < min){
                    min = dist[j];
                    idx = j;
                }
            } //해당 for문 종료 시 idx: 가장 작은 값을 가지고 있고 방문하지 않은 정점이 선택됨.

            visited[idx] = true; //뽑았어 !
            //뽑은 친구와 인접한 정점들 중 갱신할 수 있으면 갱신
            for(int j = 0 ; j<V; j++){
                if(!visited[j] && adjArr[idx][j] != 0 && dist[j] > adjArr[idx][j]){
                    dist[j] = adjArr[idx][j];
                    p[j] = idx;
                }

            }


        } //정점을 선택하는 사이클
        for(int i = 0 ; i<V; i++){
            ans += dist[i];
        }
        System.out.println(Arrays.toString(dist));
        System.out.println(ans);


    }
}

 

관련 알고리즘 문제

1) 보급로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD

SW Expert Academy

 

2) 하나로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD