[Java] 다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘(Dijkstra Algorithm)

: 그래프(ex. 도로 교통망)에서 어느 한 점에서 나머지 점들 간의 최소 거리를 구할 수 있는 알고리즘

다이나믹 프로그래밍(dp)를 활용한 최단 경로 탐색 알고리즘
이때 점 사이 가중치는 양수여야 한다. 음수의 경우 벨만-포드 알고리즘을 사용한다. (음수가 있는데 다익스트라를 사용할 경우 무한 음의 루프를 돌게 된다.)
최소힙(우선순위큐) 등을 사용해 시간복잡도를 개선 할 수 있다.(개선해야한다!)
인접행렬을 사용하기보다 인접리스트 + 우선순위큐 조합을 사용하면 시간복잡도를 O(mlog n) 까지 낮출 수 있다.

결론적으로 말하자면 다익스트라는 그때그때 최소인 경우를 찾아서 최종적으로 모든 정점에 대한 최소값을 구하는 과정이라고 볼 수 있다.

다익스트라의 구현과정을 투 스텝으로 간추리면 다음과 같다.

어느 한 점에서 갈 수 있는 도착점 중 가중치(거리)가 가장 작은 값을 찾자.
각각의 도착점까지 기존에 저장되어 있던 값과 갱신해온 값을 비교해 더 작은 값으로 수정한다.

방문하지않은(아직 처리하지 않은) 점이 없을 때까지 이 투 스텝을 반복하고 나면 각 정점까지의 최소거리가 구해진다.

🍀 step1에서 가장 작은 값을 찾는데 PriorityQueue를 사용하게 되고, step2에서 더 작은 값으로 수정하는 과정에서 dp를 사용한다.

과정을 더 자세히 파헤쳐 보자.

아래 예시는 대표적인 다익스트라 문제인 백준(https://www.acmicpc.net/problem/1753)에서 가져온 예시이다.

5개의 정점(1, 2, 3, 4, 5)와 6개의 간선정보가 주어진다.
이때 시작점은 1이고 간선 정보는 다음과 같다.
5 -> 1 : 가중치 1
1 -> 2 : 가중치 2
1 -> 3 : 가중치 3
2 -> 3 : 가중치 4
2 -> 4 : 가중치 5
3 -> 4 : 가중치 6

각 정점까지의 최소거리를 저장하기 위한 int[] 배열(answer)가 존재한다.

step1) 시작점(위 예시는 1)을 제외하고 나머지 정점은 무한대로 설정한다.
- 시작점(1) -> 시작점(1)은 자기자신이므로 0으로 세팅한다.

정점	1	2	3	4	5
최소거리	0	Integer.MAX_VALUE	Integer.MAX_VALUE	Integer.MAX_VALUE	Integer.MAX_VALUE

step2) 시작점에서 갈 수 있는 경로 (정점 2와 정점 3)를 갱신하자

정점1 -> 정점2 까지 가는데 걸리는 가중치는 2이다.
이때 answer에 저장된 2까지 가는 최소거리는 Integer.MAX_VALUE(2147483647)로 비교했을 때 2가 더 작다.
따라서 정점 2까지 가는데 걸리는 최소 거리를 2로 갱신하자.
(갱신한 값을 최소힙에 넣는다.)
정점1 -> 정점 4까지 가는데 걸리는 가중치는 3이다.
마찬가지로 answer에 저장된 3까지 가는 최소거리를 기존값과 비교하여 더 작은 값인 3으로 갱신한다.
(갱신한 값을 최소힙에 넣는다. )

정점	1	2	3	4	5
최소거리	0	2	3	Integer.MAX_VALUE	Integer.MAX_VALUE

step3) 정점1을 제외한 나머지 정점에서 cost가 가장 작은 정점을 뽑자.

- 최소힙을 사용하면 그냥 poll 하면 cost가 가장 작은 정점이 뽑힌다.
- 나머지 정점에서 cost가 가장 작은 정점은 2이다.
- 위와 같은 과정(step2)을 반복한다.

정점 2에서 갈 수 있는 경로(정점 3과 정점 4)를 갱신하자!

정점2 -> 정점3까지 가는데 걸리는 가중치는 4이다.
그렇다면 1->2->3 = 2 + 4 = 6만큼의 거리가 된다. 이미 answer배열에 저장된 3까지의 최소거리를 살펴보자.
6(정점1 -> 정점2 -> 정점3)과 3(정점1 -> 정점3)을 비교하면 저장되어 있던 값이 더 작으므로 갱신하지 않는다.
정점2 -> 정점4까지 가는데 걸리는 가중치는 5이다.
그렇다면 (1->2->4) = 2+5 = 7만큼의 거리가 된다. answer배열에 저장되어 있던 4까지의 최소거리를 살펴보자.
Integer.MAX_VALUE(2147483647)로 비교했을 때 7이 더 작다. 정점4까지의 최단거리를 7로 갱신한다.

정점	1	2	3	4	5
최소거리	0	2	3	7	Integer.MAX_VALUE

step4) 정점 1,정점2를 제외한 나머지 정점에서 cost가 가장 작은 정점을 뽑자.

방문하지 않은 정점이 존재하지 않을 때까지 반복하면 answer에 저장된 배열을 최소거리가 된다.

이때 값이 Integer.MAX_VALUE로 초기값과 변하지 않은 정점이 있다면 시작점에서 도착할 수 없는 정점!

최종 배열은 아래와 같다.

정점	1	2	3	4	5
최소거리	0	2	3	7	Integer.MAX_VALUE

이제 이 과정을 코드화 해보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * p1753_최단경로
 * : 다익스트라 알고리즘(우선순위큐 사용)
 */
public class Practice {
    static int V,E,K; //정점의 개수, 간선의 개수, 시작 정점의 번호
    static List<List<Edge2>> adjList = new ArrayList<>();
    static int[] answer;
    static boolean[] check;
    static PriorityQueue<Edge2> pq = new PriorityQueue();

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(br.readLine());

        answer = new int[V+1];
        check = new boolean[V+1];

        for(int i=0; i<=V; i++){
            adjList.add(new ArrayList<Edge2>());
        }

        //인접리스트에 값 세팅
        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            adjList.get(u).add(new Edge2(v,w));
        }

        //answer 배열에 시작점:0,외의 다른점: 무한대로 세팅해두기
        for(int i=0; i<=V; i++){
            if(i == K) answer[i] = 0;
            else answer[i] = Integer.MAX_VALUE;
        }

        //우선순위 큐에 시작점 삽입
        pq.add(new Edge2(K,0));

        //함수실행
        getShortestPaths();

        //출력
        print();
    }
    static void getShortestPaths(){
        while(!pq.isEmpty()){
            Edge2 edge2 = pq.poll(); //cost 가장 작은거 튀어나옴.
            int eDest = edge2.dest;

            if(!check[eDest]){
                check[eDest] = true; //pq에서 꺼내고 나서 방문처리

                for(Edge2 tmp : adjList.get(eDest)){
                    int min = Math.min(answer[tmp.dest], tmp.cost+answer[eDest]);
                    answer[tmp.dest] = min;
                    pq.add(new Edge2(tmp.dest,min));
                }
            }
        }
    }
    static void print(){
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=V; i++){
            if(answer[i] == Integer.MAX_VALUE){
                sb.append("INF"+"\n");
            }
            else sb.append(answer[i]+"\n");
        }
        System.out.println(sb.toString());
    }
}
class Edge2 implements Comparable<Edge2>{
    int dest;
    int cost;

    public Edge2(int dest, int cost){
        this.dest = dest;
        this.cost = cost;
    }


    @Override
    public int compareTo(Edge2 edge2) {
        return this.cost - edge2.cost; //오름차순(작은것부터)
    }
}

주의 할 점)

방문 처리를 pq에서 poll 하고난 후에 해야 한다.
pq에서 나오는 값이 남은 정점 중 최소거리에 해당하는 값인데 이걸 poll하기 전엔 알 수가 없으니까!!

저작자표시 (새창열림)

다익스트라 알고리즘(Dijkstra Algorithm)

검색 태그

티스토리툴바