최단 경로 알고리즘

최단 경로 알고리즘

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다.

최단 경로 알고리즘 특징

최단 경로 알고리즘에는 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 그대로 적용된다는 특징이 있다.

또한 최단 경로 문제는 보통 그래프를 이용해서 표현하는데 각 지점은 그래프에서 노드로 표현되고, 지점 간 연결된 도로는 그래프에서 간선으로 표현된다.

최단 경로 알고리즘에는 다익스트라 알고리즘, 플로이드 워셜 알고리즘, 벨만 포드 알고리즘 등과 여러 알고리즘이 있다.
여기서는 다익스트라 알고리즘과 플로이드 워셜에 대해 알아본다.

다익스트라 알고리즘

다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
다익스트라 알고리즘이 동작하기 위해서는 하나의 조건이 있는데, ‘음의 간선’이 없어야 한다는 것이다.

핵심

다익스트라 알고리즘의 동작 원리는 다음과 같다.

0. 노드 방문 여부 테이블 초기화, 출발 노드로 현재 노드 설정, 최단 거리 테이블 초기화
   • 출발 노드의 거리는 0, 나머지 노드의 거리는 무한대로 설정한다.
1. 현재 노드까지의 거리와 현재 노드에서 방문할 수 있는 노드들의 거리를 계산하여 최단 거리 테이블을 갱신, 현재 노드를 방문 처리 한다.
   • (출발 노드에서 현재 노드까지 이동한 거리 + 현재 노드에서 방문할 노드까지의 거리) < 최단 거리 테이블의 해당 노드 값이라면 더 적은 비용으로 이동 가능하므로 최단 거리 테이블을 갱신한다.
   • 이후, 현재 노드를 방문 처리 한다.
2. 방문하지 않는 노드 중 최단 거리가 가장 짧은 노드를 선택한다.
3. 위 1, 2번 과정을 반복한다.

다익스트라 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 2번 과정과 같이 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문이다.

위 과정을 보면 다익스트라 알고리즘은 '방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택'하는 과정을 반복한다.
이를 통해 선택된 노드는 '최단 거리'가 완전히 선택된 노드이므로, 더 이상 알고리즘을 반복해도 최단 거리가 줄어들지 않는다.
이를 통해 다익스트라 알고리즘이 진행되면서 한 단계당 하나의 노드에 대한 최단 거리를 확실하게 찾는 것으로 이해할 수 있다.

위 동작 원리대로 구현한 다익스트라 알고리즘은 O(V^2), [V = 노드 개수]의 시간 복잡도를 가진다.
매 단계(O(V))마다 최단 거리가 가장 짧은 노드를 선택하기 위해 최단 거리를 담는 1차원 리스트의 모든 원소를 순차 탐색(매 단계마다 O(V))하기 때문이다.
따라서 노드의 개수 및 간선의 개수가 많을 때에는 '개선된 다익스트라 알고리즘'을 이용하여 구현하여야 O(V^2)의 시간 복잡도를 최적화 할 수 있다.

개선된 다익스트라 알고리즘

개선된 다익스트라 알고리즘은 Heap 자료구조를 사용한다.
힙 자료구조를 이용하게 되면, 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 짧은 거리의 노드를 더 빠르게 찾을 수 있다.

Heap 자료구조
힙 자료구조는 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나다.
우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징이다.
우선순위 큐를 구현할 때는 내부적으로 최소 힙 또는 최대 힙을 이용한다.
최소 힙은 값이 낮은 데이터가 높은 우선순위를 가지며, 최대 힙은 값이 큰 데이터가 높은 우선순위를 가진다.
자바에서는 PriorityQueue를 통해 우선순위 큐를 이용할 수 있으며, 기본적으로 최소 힙을 이용하여 우선순위를 처리한다.

이를 통한 알고리즘의 흐름을 정리해보면 다음과 같다.

0. 출발 노드를 우선순위 큐에 삽입한다.
   • 우선순위 큐에 삽입할 때, 출발 노드의 거리는 0이다.
1. 우선순위 큐에 삽입된 노드를 꺼낸다. 해당 노드를 이미 처리한 적이 있다면 무시한다.
2. 1번에서 꺼낸 노드를 방문처리 하고, 해당 노드와 인접한 노드를 우선순위 큐에 삽입한다.
   • 우선순위 큐에 삽입할 때, 출발 노드로부터 인접한 노드의 거리는 (꺼낸 노드의 거리 + 인접 노드까지의 거리)이다.
   • 인접 노드까지의 거리가 최단 거리 테이블을 비교하여 더 작으면 최단 거리 테이블을 갱신한다.
3. 우선순위 큐에서 더 이상 꺼낼 노드가 없을 때 까지 1, 2번 과정을 반복한다.

코드로 나타내자면 다음과 같다.

// 0. 출발 노드 설정
priorityQueue.add(new Node(start, 0));
shortest[start] = 0;

// 다익스트라 알고리즘 수행
while (!priorityQueue.isEmpty()) {
   // 1. 우선순위 큐에서 노드를 꺼냄. 이미 처리한 적이 있다면 무시한다.
   Node poll = priorityQueue.poll();
   int now = poll.node; // 꺼낸 노드로 이동. now = 현재 노드
   if (!visited[now]) {
       // 2. 현재 노드를 방문처리하고 현재 노드와 인접한 노드를 우선순위 큐에 넣는다.
       visited[now] = true;
       for (int i = 1; i < n+1; i++) { // i = 목적지 노드
           // pathNodeCost = 현재 노드에서 목적지 노드까지의 비용
           int pathNodeCost = paths[now][i];
           if (now != i && pathNodeCost != INF) { // INF = 무한대
               // fullCost = 출발 노드로부터 목적지 노드까지의 비용
               // poll.cost = 출발 노드로부터 현재 노드까지의 비용
               int fullCost = poll.cost + pathNodeCost;
               // 기존 최단 거리와 현재 노드에서의 최단 거리를 비교하여 최단 거리 테이블 갱신
               shortest[i] = Math.min(shortest[i], fullCost);
               // 우선순위 큐에 넣음
               priorityQueue.add(new Node(i, fullCost));
           }
       }
   }
}

...

private static class Node {
   public int node; // 이동할 노드 번호
   public int cost; // 이동할 노드까지의 비용

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

이와 같은 흐름을 통해 개선된 다익스트라 알고리즘은 O(E log V), [V = 노드 개수, E = 간선 개수]의 시간 복잡도를 보장한다.

플로이드 워셜 알고리즘

플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘이다.

핵심

단계마다 거쳐가는 노드를 기준으로 알고리즘을 수행한다는 점에서는 다익스트라 알고리즘과 같다.

하지만 플로이드 워셜 알고리즘은, 매번 방문하지 않은 노드 중에서 최단거리를 갖는 노드를 찾지 않는다.
N개의 노드를 가질 때, 알고리즘 상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다.
N번의 단계에서 매 단계동안 O(N^2)의 시간이 소요되기 때문에, 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N^3)이 된다.

또한 플로이드 워셜 알고리즘은 2차원 리스트에 최단 거리 정보를 저장한다.
모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문이다.
2차원 리스트를 처리해야 하므로 N번의 단계에서 매번 O(N^2)의 시간이 소요되는 것이다.

플로이드 워셜 알고리즘은 다이나믹 프로그래밍이라는 특징이 있다.
노드의 개수 N번 만큼의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신해야 하기 때문에 다이나믹 프로그래밍으로 볼 수 있다.

아래는 플로이드 워셜 알고리즘의 동작을 설명한다.

0. 그래프를 통해 최단 거리 테이블을 초기화한다.
   • 2차원 리스트로 각 노드의 인접 노드로의 거리로 초기화한다.
1. K번의 반복을 통해 K 노드를 거쳐가는 경우를 고려한다.
   1. 현재 노드를 제외하고 N - 1개의 노드 중에서 서로 다른 노드 (A, B) 쌍을 선택한다.
   2. 최단 거리 테이블에 기록된 A에서 B로 가는 최소 비용과, A에서 K를 거쳐 B로 가는 비용을 비교하여 더 작은 값으로 최단 거리 테이블을 갱신한다.
   3. 이를 점화식으로 나타내면 D_ab = min(D_ab, D_ak + D_kb)와 같다.

1. K번의 반복을 통해 K 노드를 거쳐가는 경우를 고려한다에서 출발지 A, 목적지 B, 경유 노드 K가 모두 다를 경우만 확인하면 된다.
A, B가 같은 경우는 출발지와 목적지가 같기 때문에 비용이 항상 0으로 고려하지 않아도 된다.
A, K가 같은 경우는 출발지와 경유 노드가 같다. 따라서 출발지에서 목적지로 경유 노드 없이 바로 이동하는 경우와 동일하기 때문에 고려하지 않아도 된다.
B, K가 같은 경우 역시 마찬가지다. 목적지와 경유 노드가 같기 때문에 출발지에서 경유 노드 없이 바로 목적지로 이동하는 경우와 동일하다. 이 역시 고려하지 않아도 된다.

이를 코드로 나타내자면 다음과 같다.

// 최단거리 테이블 초기화
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        if (i == j) {
            arr[i][j] = 0;
        } else {
            arr[i][j] = INF;
        }
    }
}

// 경로 입력 받기
for (int i = 0; i < m; i++) {
    st = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    arr[a][b] = arr[b][a] = 1;
}

// 플로이드 워셜 수행
for (int K = 1; K <= n; K++) { // 경유 노드 K
    for (int A = 1; A <= n; A++) { // 출발 노드 A
        for (int B = 1; B <= n; B++) { // 목적지 노드 B
            // 경유 노드를 거쳐가는 경우가 더 적은 비용이 든다면 최단거리 테이블 갱신
            arr[A][B] = Math.min(arr[A][B], arr[A][K] + arr[K][B]);
        }
    }
}