[210517] 다익스트라 알고리즘 - java

 

.

 

다익스트라 알고리즘(Dijkstra Algorithm)은 그래프에서 두 정점 간의 최단 경로를 찾는 알고리즘이다. 

시작점과 끝점이 주어져있을 때 사용할 수 있으며, 이를 응용해서 최단 경로 트리를 만드는 것도 가능하다. 

 

 

설명을 위해, 임의로 위와 같은 그래프를 만들었다. 가중치가 있는 방향 그래프다. 

a에서 e로 가는 최단 경로를 구한다고 가정하자. 정점이 5개 있기 때문에, 크기가 5인 1차원 배열에 최단 거리의 값을 저장할 것이다. 

 

 

1) 시작점과 연결된 모든 정점에 대해서, 시작점과 해당 정점의 최단 거리를 구한다. 

시작점인 a와 연결된 정점은 b와 c가 있다. 

a에서 b를 잇는 간선의 가중치는 3, a에서 c의 경우는 4이므로 아래와 같이 표를 채웠다. 

	a	b	c	d	e
a	∞	3	4	∞	∞

최단거리가 구해지지 않은 부분은 ∞로 채웠다. 

 

 

2) 위에서 방문한 정점과 연결된 모든 정점에 대해 다시 1을 수행한다. 

a→b, a→c에 대한 거리를 구했으니, 이제 b, c와 이어진 간선에 대한 거리를 구해야 한다. 

큐를 생각하면 쉽다. 

Queue에 나온대로, a를 방문할 때 Queue에서 a를 제거하고 b, c를 넣는다. 그리고 다음 수행 때 b를 제거한 뒤, b와 연결되어 있는 e를 넣는다. 

 

 

표를 다음과 같이 채울 수 있다. a에서 b까지의 거리 3에 b에서 e까지의 거리 7을 더해서 배열에 저장한다. 

	a	b	c	d	e
a	∞	3	4	∞	10

 

정점 c와 연결된 정점도 방문한다. a에서 d까지의 최단거리로 (a에서 c까지의 거리 4 + c에서 d까지의 거리 2) = 6을 저장한다. 

 

	a	b	c	d	e
a	∞	3	4	6	10

 

 

2 수행을 마친 후 큐의 모습은 아래와 같다. 

 

3) e에 방문하나, e에서 갈 수 있는 정점이 없기 때문에 아무것도 하지 않는다. 

 

4) d가 방문할 수 있는 정점에 방문한다. 

 

 

d에서 e로 가는 거리는 1이므로, 이 거리를 이용했을 때 a에서 e로 가는 거리는 a에서 d로 가는 거리에 d에서 e로 가는 거리를 더한 것과 같다. 즉, 6+1로 7인데, 기존에 배열에 a에서 e로 가는 거리로 저장되어 있던 값이 10보다 작다. 따라서, 배열의 값을 7로 바꾼다. 

	a	b	c	d	e
a	∞	3	4	6	7

 

모든 정점에 대한 방문을 완료했으므로 수행을 마친다. 

 

 

 

우선순위 큐를 사용하면 더 효율적으로 코드를 작성할 수 있다. 거리가 짧은 노드부터 탐색을 하므로 최단거리를 찾는 데 더 용이하다. 

 

 

- 소스 코드 

 

public static class Node implements Comparable<Node>{
        int point; // 정점의 좌표
        int cost; // 해당 정점까지의 거리

        public Node(int point, int cost) {
            this.point = point;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node n) {
            // 가중치를 기준으로 오름차순 정렬
            return this.cost - n.cost;
        }
    }

    public static void main(String[] args) {

        int graph[][] = {{0, 7, 2, 0, 0}, // 가중치가 있는 방향 그래프
                {0, 0, 0, 0, 3},
                {0, 2, 0, 2, 0},
                {0, 0, 0, 0, 9},
                {0, 0, 0, 0, 0}};

        int distance[] = new int[graph.length]; // 최단거리를 저장하는 배열 graph.length = 5
        boolean isChecked[] = new boolean[graph.length]; // 정점 방문 여부를 저장하는 배열. 한 번 방문한 정점에 다시 방문할 필요 x
        Arrays.fill(distance, Integer.MAX_VALUE);

        int start = 0; // 시작점
        int end = 4; // 도착점

        distance[start] = 0; // 시작점의 비용은 0으로 설정한다.

        Queue<Node> queue = new PriorityQueue<>(); // 우선순위 큐를 사용해서 탐색
        queue.add(new Node(start, distance[start])); // 시작점에서 탐색을 시작하기 위해서 큐에 저장해준다. 

        // queue가 빌 때까지 반복해서 탐색
        while(!queue.isEmpty()){
            // 1. queue의 맨 앞에 있는 원소를 가져온다.
            Node node = queue.poll();

            // 1-1. 큐에 저장된 거리값이 탐색을 수행해서 바뀐 거리값보다 크다면 최단경로 값이 갱신되었다는 뜻이다. 
            // 탐색을 하지 않고 넘어간다. 
            if(node.cost > distance[node.point])
                continue;

            for(int j = 0 ; j < graph.length ; j++){
                // 2. 그 정점과 연결된 정점이 존재하고, 그 정점까지의 거리가 distance에 저장된 거리보다 작다면 distance 값을 갱신한다.
                if(j != node.point && graph[node.point][j] != 0 && distance[j] > graph[node.point][j] + node.cost){
                    distance[j] = graph[node.point][j] + node.cost;
                    // 3. 방문한 정점을 queue에 넣는다.
                    queue.add(new Node(j, distance[j]));
                }

            }
        }

        // 도착점에 대한 최단거리 출력
        System.out.println(distance[end]);

    }

 

 

 

- 참고 자료 

https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전