<알고리즘> 1. 다익스트라 JAVA

가. 무엇인가

 a. 최단경로

  -  시작정점부터 모든 정점으로 가는 최단경로를 구하는 알고리즘 

     => 가중치가 양수일 경우에만 사용가능

  -  진행

      0. 모든 정점이 가지고 있는 가중치합(시작정점부터 도착정점까지의 최단경로)을 INF(엄청큰값) 초기화한다.

      1. 현재 정점(동그리미)이 가진 간선들중 가장 최소값을 가지는 간선의 정점을 방문한다.

          => 이때 방문 정점이 가지고 있는 가중치합은 여러 정점을 거쳐왔을수도 있다.

      2. 현재 경로의 가중치합과 방문정점이 가지고 있는 가중치의 합을 비교해서 최소값으로 업데이트한다. 

      3. 현재 시점에서 가중치합이 더 작았다면 방문정점에서 다시 1번을 수행한다. 

 

나. 구현하기 

 a. 배열

public class 다익스트라 {

    public static void main(String[] args) {
        int N = 5;
        List<Edge>[] path = new LinkedList[N];
        for(int i = 0; i < N; i++) {
           path[i] = new LinkedList<>();
        }
        path[0].add(new Edge(2,1));
        path[0].add(new Edge(1,4));
        path[1].add(new Edge(3,1));
        path[2].add(new Edge(1,2));
        path[4].add(new Edge(0,2));
        path[4].add(new Edge(2,3));
        path[4].add(new Edge(3,7));
        new 다익스트라().최단경로(4, path);
    }
    
    public void 최단경로(int start, List<Edge>[] path){

        int N = path.length;
        boolean[] visited = new boolean[N];
        int[] dist = new int[N];  // 시작점과 정점의 최단경로 가중치
        int[] prev = new int[N]; // 이전 방문 정점
        Arrays.fill(dist,INF);
        Arrays.fill(prev,-1);

        dist[start] = 0;
        // 시작을 가장작은 경로값을 가지는 것이므로 0으로 초기화

        prev[start] = -1;


        for(int i = 0; i < N; i++) {
            // 모든 정점을 방문하는 순간 끝이므로 N번 반복
            int min = INF;
            int minVertex = -1;

            // 가장 최소가 되는 정정부터 탐색
            for(int j = 0; j < N; j++) {
                if(!visited[j] &&  dist[j] < min){
                    min = dist[j];
                    minVertex = j;
                }
            }

            visited[minVertex] = true;

            for(Edge adjEdge : path[minVertex]){
                int newDist = dist[minVertex] + adjEdge.weight;
                // 이전까지의 가중치 + 가려고하는 정점의 가중치

                int currentDist = dist[adjEdge.vertex];

                if(!visited[adjEdge.vertex] && newDist < currentDist){
                    // 경로 업데이트
                    dist[adjEdge.vertex] = newDist;
                    prev[adjEdge.vertex] = minVertex;
                }
            }
        }

        for(int i = 0; i < N; i++) {
            int k = i;
            List<Integer> order = new ArrayList<>();
            while(k != -1){
                order.add(k);
                k = prev[k];
            }
            Collections.reverse(order);
            for(int v : order ){
                System.out.print(v+" -> ");
            }
            System.out.println();
        }

    }

    public int INF = Integer.MAX_VALUE;

    private static class Edge {
        int vertex;
        int weight;

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

    }
}

 

 b. 우선순위큐

  -  경로가 최소인 부분을 찾을때 우선순위 큐를 사용해서 찾을 수도 있다.

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

    public static void main(String[] args) {

        int N = 5;
        List<Edge>[] path = new LinkedList[N];
        for(int i = 0; i < N; i++) {
            path[i] = new LinkedList<>();
        }
        path[0].add(new Edge(2, 1));
        path[0].add(new Edge(1, 4));
        path[1].add(new Edge(3, 1));
        path[2].add(new Edge(1, 2));
        path[4].add(new Edge(0, 2));
        path[4].add(new Edge(2, 3));
        path[4].add(new Edge(3, 7));
        new 다익스트라_우선순위큐().최단경로(4, path);
    }
    public int INF = Integer.MAX_VALUE;

    public void 최단경로(int start, List<Edge>[] path){
        int N = path.length;
        boolean[] visited = new boolean[N];
        int[] prev = new int[N];
        int[] dist = new int[N];
        Arrays.fill(prev,-1);
        Arrays.fill(dist,INF);

        dist[start] = 0;

        Queue<Edge> queue = new PriorityQueue<>();
        queue.add(new Edge(start,dist[start]));

        for(int i = 0; i < N; i++) {
            Edge minVertex = queue.poll();

            if(visited[minVertex.vertex]) continue;
            visited[minVertex.vertex] = true;

            for(Edge adj : path[minVertex.vertex] ){
                int newDist = dist[minVertex.vertex] + adj.weight;
                int current = dist[adj.vertex];
                if(!visited[adj.vertex] && newDist < current){
                    dist[adj.vertex] = newDist;
                    prev[adj.vertex] = minVertex.vertex;
                    queue.add(new Edge(adj.vertex,newDist));
                }
            }
        }

        System.out.println(Arrays.toString(dist));
        for(int i = 0; i < N; i++) {
            int k = i;
            List<Integer> order = new ArrayList<>();
            while(k != -1){
                order.add(k);
                k = prev[k];
            }
            Collections.reverse(order);
            for(int v : order ){
                System.out.print(v+" -> ");
            }
            System.out.println();
        }

    }
    private static class Edge implements Comparable<Edge>{
        int vertex;
        int weight;

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

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

 

참고 : www.aladin.co.kr/shop/wproduct.aspx?ItemId=115240038

자바와 함께하는 자료구조의 이해