최단 경로 문제 (1) 다익스트라 알고리즘을 중심으로

1. 들어가기

어떤 A지점에서 다른 B지점으로 이동하는 경로는 다양할 수 있다. 이는 네트워크에서도 마찬가지로 적용되는 부분이다. 연결 경로가 다양하게 존재할 수 있다. 경로가 다양하게 존재할 수 있는 가운데, 주목해야할 것은 가장 짧은 경로의 경우다. 이를 최단 경로라고 부른다. 최단 경로 문제는 다양한 경로 중 적은 비용으로 빠르게 이동하는 경로를 찾는 문제다. 이번 글에서는 최단 경로의 개념 및 이와 관련된 다익스트라 알고리즘에 대해 알아보고, 예제 문제를 살펴볼 것이다.
 

2. 최단경로

어떤 가중치가 부여된 방향 그래프가 있다고 하자. 가중치가 부여된 그래프의 비용은 가중치를 계산하여 최단거리를 결정할 수 있다. 이때 가중치를 비용이라고 한다면 경로의 합이 가장 적은 경우가 최단 거리가 된다. 그리고 가중치를 효과라고 한다면 가중치의 합이 큰 경로가 최단 거리가 될 수 있다. 다시 말해, 가중치의 기준을 어느 것이 두었느냐에 따라 최단경로를 결정짓는 경우가 가중치의 합이 최소인 경우가 될 수도 있고, 가중치의 합이 최대인 경우가 될 수도 있다. 다음 예시를 통해 가중치를 비용으로 두었을 때, 최소가 되는 경우를 모두 구해보기로 하자. 
 

[그림 1] 그래프

 그래프가 위 [그림 1]과 같이 존재한다고 하면,  a에서 e까지 이동하는 경로는 다음과 같이 구할 수 있다.
(1) a - b - c - d - e : 15 + 17 + 8 + 3 = 43
(2) a - b - c - e : 15 + 17 + 10 = 42
(3) a - f - b - c - d - e : 2 + 10 + 17 + 8 + 3 = 40
(4) a - f - b - c - e : 2 + 10 + 17 + 10 = 39
(5) a - f - h - e : 2 + 14 + 17 = 33
(6) a - f - g - h - e : 2 + 9 + 10 + 17 = 38
이 중 가장 적은 비용을 가지는 경로는 (5)에 해당하여, 그래프의 최단경로는 (5)가 된다. 위 문제에 최단 경로 알고리즘을 적용한다면 다익스트라(Dijkstra) 알고리즘을 적용할 수 있다. 다익스트라 알고리즘은 시작점으로부터 최단 경로를 갖는 꼭짓점들을 순차적으로 탐색하는 알고리즘이다. 다익스트라 알고리즘의 규칙을 자세하게 알아 본 뒤 실제 문제에 적용해보도록 하자.
- 규칙 1 : 다익스트라 알고리즘은 가중치가 존재하는 그래프에 적용할 수 있다. 다만 가중치가 양수여야 한다. (음의 가중치가 존재하는 경우에는 음수 사이클이 존재하지 않는 경우에 한해서 벨만-포드 알고리즘을 적용한다. 벨만-포드 알고리즘은 다음 글에서 설명해보겠다.)
- 규칙 2 : 시작점을 제외한 모든 점에 매우 큰 값인 INF를 할당한다.
다익스트라 알고리즘으로 BFS로 가장 가까운 순서를 찾을 때 PriorityQueue를 적용하면, 이 경우 시간복잡도 O((V+E) log V)가 된다. 그리고 모든 꼭짓점이 출발지에서 도달 가능하면 최종적으로 O(E log V) 가 된다. (E는 경로(간선) 수, V는 꼭짓점(노드)의 수)

3. 정리

다익스트라 알고리즘을 적용하여 최단거리 문제를 풀면 다음과 같은 절차를 거친다.

1) 다익스트라 알고리즘을 적용이 가능한지를 확인(모든 경로가 양의 가중치를 가지는 가를 확인)
2) 출발점을 제외한 모든 점에 매우 큰 값인 INF를 할당함
3) PriorityQueue로 우선 순위가 매겨진 값을 뽑는다.
4) 각 꼭짓점을 방문할 때 값을 할당하는 조건으로는 현재의 가중치와 인접노드의 가중치 합 보다 더 작다면 이 값으로 최단 거리 값으로 사용하는 변수에 값을 갱신한다.
5) 시작 점과 인접한 모든 꼭짓점에 이를 적용하고, 모든 꼭짓점에 방문할 때까지 이를 반복한다. 
 

4. 구현

import java.io.*;
import java.util.*;

class Node{
    int to;
    int weight;

    public Node(int to, int weight){
        this.to = to;
        this.weight = weight;
    }
}

public class Main {
    static int N, M, K, X;
    static ArrayList<ArrayList<Node>> graph;
    static HashMap<Integer, Integer> map;
    final static int INF = Integer.MAX_VALUE;
    
    public static int dijkstra(int n, int start, int end){
        PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> x.weight - y.weight);
        pq.offer(new Node(start, 0));

        int[] dist = new int[n+1];
        for(int i=0; i< n+1; i++){
            dist[i] = INF;
        }
        dist[start] = 0;
        boolean[] visited = new boolean[n+1];

        while(!pq.isEmpty()){
            Node curNode = pq.poll();

            if(visited[curNode.to]){
                continue;
            }
            visited[curNode.to] = true;

            for(int i=0; i<graph.get(curNode.to).size(); i++) {
                Node adjNode = graph.get(curNode.to).get(i);
                if(!visited[adjNode.to] && dist[adjNode.to] > curNode.weight + adjNode.weight){
                    dist[adjNode.to] = curNode.weight + adjNode.weight;
                    pq.offer(new Node(adjNode.to, dist[adjNode.to]));
                }
            }
        }

        for(int i=1; i<dist.length; i++){
            map.put(i, dist[i]);
        }
        return dist[end];
    }

    public static void main(String[] args) {
        N = 4;
        M = 4;
        K = 1;
        X = 1;
        
        String[] graphArr = new String[]{"1 2", "1 3", "2 3", "2 4"};

        graph = new ArrayList<>();
        map = new HashMap<>();

        for(int i=0; i<N+1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            int a = Integer.parseInt(graphArr[i].split(" ")[0]);
            int b = Integer.parseInt(graphArr[i].split(" ")[1]);

            graph.get(a).add(new Node(b, 1));
        }

        dijkstra(N, X, N);

        StringBuffer sb = new StringBuffer();

        for(int i=1; i<=N; i++){
            if(map.get(i)!= null){
                if(K == map.get(i)){
                    sb.append(i + " ");
                }
            }
        }

        if(sb.length()>0) System.out.print(new String(sb) + "\n"); // 2 3
        else System.out.println("-1");

        sb.setLength(0);
    }
}

 

5. 다익스트라 구현 시 유의할 점

- 가중치가 양수인 경우에만 사용할 수 있음을 유의한다.
- 각 점들의 최단경로의 거리는 INF로 초기화 한다.
- 위 예시는 가중치가 1인 경우다. 가중치가 서로 다른 경우에도 적용해 보자.

 
참고문헌 : 컴퓨팅 사고력을 키우는 이산수학 / 한빛아카데미, 나무위키(https://namu.wiki/w/다익스트라%20알고리즘)