[알고리즘] 최단 경로 - Dijkstra 알고리즘

1. 개요

---

최단 경로 알고리즘은 크게 두 가지로 분류됩니다.

1. one-to-all : 하나의 정점에서 다른 모든 정점으로의 최단 경로를 구한다. (Dijkstra 알고리즘, 벨만-포드 알고리즘)
2. all-to-all : 모든 정점에 대해 자신을 제외한 다른 모든 정점으로의 최단 경로를 구한다. (Floyd-Warshall 알고리즘)

Dijkstra 알고리즘은 one-to-all에 속하며, 이 외에도 벨만 포드 알고리즘이 있습니다.
벨만 포드는 음의 가중치일 때 사용되는데, 실세계에서 음의 가중치를 가질만한 것들이 잘 없기 때문에 잘 쓰이진 않습니다.

2. 다익스트라(Dijkstra) 알고리즘이란?

---

Dijkstra 알고리즘의 특징은 다음과 같습니다.

1. one-to-all (하나의 정점에서 다른 모든 정점으로의 최단 경로를 구한다.)
2. 음의 가중치를 포함할 수 없다. (간선의 가중치에 음수가 포함된다면 대안으로, 벨만 포드 알고리즘이 있다.)

다음과 같은 그래프가 있다고 해보자.

[그림 1] 예제 그래프

Floyd-Warshall은 all-to-all이라 거리 정보를 담을 2차원 배열이 필요한데 반해, 다익스트라는 1차원 배열을 사용한다. (one-to-all)

또, Dijkstra 알고리즘은 DP를 기반으로 동작하는데 예를 들어, 1->3으로 가는 비용이 7이었다고 가정해보겠습니다. 이때 1->2로 가는 비용이 2이고, 2->3으로 가는 비용이 3이라면, 처음 1->3으로 셋팅되어있던 배열에는 1->2->3 경로의 값으로 갱신된다.

즉, 1->3으로 가기위해 2를 거쳐야한다는 사실을 기존에 구해놨던 1->2 의 거리 값과 2->3 의 거리 값을 가지고 판단하기 때문이다.

3. 코드

---

public class Main {

    private static final int INF = 1_000_000_000;

    private static int[][] edge;
    private static int[] dist;

    public static void main(String[] args) {
        dist = new int[6];
        Arrays.fill(dist, INF);
        edge = new int[6][6];
        
        edge[5][1] = 1;
        edge[1][2] = 2;
        edge[1][3] = 3;
        edge[2][3] = 4;
        edge[2][4] = 5;
        edge[3][4] = 6;
    }
    
    private static void dijkstra(int start) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(start);
        dist[start] = 0; // 자기 자신으로의 거리는 0이다. 
        
        while (!pq.isEmpty()) {
            Integer cur = pq.poll();
            
            for (int i = 1; i <= 6; i++) {
                if (edge[cur][i] != 0) {
                    if (dist[i] > dist[cur] + edge[cur][i]) {
                        dist[i] = dist[cur] + edge[cur][i];
                        pq.add(i);
                    }
                }
            }
        }
    }
}

 

4. 참고자료

---

[1] blog.naver.com/ndb796/221234424646