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

그래프를 탐색하는 알고리즘에는 대표적으로 DFS, BFS가 있고 이들은 모두 간선을 이용할때 가중치가 없는 경우이다.

특히 BFS의 경우 가중치가 없는 경우 최단경로를 구할때 사용하지만 노드 사이의 간선을 이용할 때 가중치가 있는 그래프가 있고, 시작점으로 부터 목적지까지의 최소한의 가중치 비용을 갖는 최단 경로를 계산해야할 때는 다익스트라 알고리즘, 플로이드-와샬 알고리즘, 벨만-포드 알고리즘을 사용해야합니다.

오늘부터 이 세개의 알고리즘을 공부하며 포스팅 할 계획으로, 다익스트라 알고리즘부터 시작하겠습니다.

 

먼저, 다익스트라 알고리즘은 하나의 시작점에서 다른 모든 정점까지의 최단 거리를 구할 수 있습니다. 단, 간선의 비용은 음수이면 안됩니다. (음수의 간선일 경우 플로이드-와샬 알고리즘을 사용합니다)

위와 같은 그래프가 있다고 가정하겠습니다. 여기서 시작점은 1이고 각 노드로 가는 최단 비용은 아래와 같을 것입니다.

1 : 0, 2 : 4, 3 : 1, 4: 3, 5 : 8, 6 : 7, 7 : 6 이렇게 1번 노드에서 1번노드는 0의 비용만큼, 2번 노드까진 4가 들고, 3번 노드에는 1만큼 이런식으로 최단 거리(최단 비용)이 필요합니다.

다익스트라 알고리즘은 BFS와 비슷한 형태입니다. 그러나 큐가 아니라 우선순위 큐를 사용하고 여기에는 정점번호와 최단거리의 쌍을 넣습니다. 우선순위 큐를 사용하면 정점까지 최단 거리를 기준으로 정렬해 현재 위치에서 아직 방문하지 않은 정점 중 가장 가까운 점을 찾을 수 있습니다. 

해당 정점까지 현재 찾은 최단 거리를 구하기 위해 distance배열을 사용하겠습니다. distance[2] = 4라는 의미는 현재 2번정점까지 가는 최단 거리는 4라는 것입니다. 

1. 현재 정점 u에서 인접한 정점을 모두 검사한다. 이중 방문하지 않은 정점이 v라 하면 u에서 v까지의 가중치를 더해 v까지 가는 비용을 구합니다. 이 비용이 distance[v]보다 작다면 distance[v]를 갱신하고 v, distance[v]를 우선순위 큐에 넣어줍니다.

위의 과정을 우선순위 큐가 빌 때까지 반복하면 시작점으로 부터 모든 정점까지의 최단거리를 구할 수 있습니다.

 

# 코드

다익스트라 알고리즘의 코드를 올리기 전 위에 만든 그래프를 생성하는 코드입니다. (인접리스트 사용)

public class Graph {
        int n;
        List<List<Node>> sparseList;
        public Graph(int n) {
            this.n = n;
            this.sparseList = new ArrayList<>();
            for (int i=0; i< n+1; i++)
                sparseList.add(new ArrayList<>());
        }
 
        /**
         * 양쪽으로 연결
         */
        public void addEdge(int u, int v, int w){
            sparseList.get(u).add(new Node(v, w));
            sparseList.get(v).add(new Node(u, w));
        }
 
        //한쪽으로 연결
        public void addEdgeSingle(int u, int v, int w) {
            sparseList.get(u).add(new Node(v, w));
        }
}
 
public class Main {
    public static void main(String[] args) throws IOException {
        int N = 7;
        Graph graph = new Graph(N);
        graph.addEdge(1, 2, 5);
        graph.addEdge(1, 3, 1);
        graph.addEdge(3, 4, 2);
        graph.addEdge(4, 5, 5);
        graph.addEdge(4, 2, 1);
        graph.addEdge(4, 7, 3);
        graph.addEdge(2, 6, 3);
        graph.addEdge(2, 7, 3);
        graph.addEdge(6, 7, 2);
    }
}

 

#1. 우선순위 큐를 사용한 다익스트라 알고리즘 코드

이 코드의 경우 시간복잡도는 E+ElogE로 O(ElogE)가 필요합니다. 공간복잡도는 O(E)

1. E : 그래프의 모든 간선을 방문함

2. ElogE : 우선순위 큐에 원소를 삽입하거나 삭제할 때 logV라는 시간이 필요. 우선순위 큐에 삽입되는 원소들이 V개보다는 크기때문에 E라고 해야한다. 그 이유는 이미 방문한 정점이어도 새로 찾은 경로가 최단거리라면 우선순위 큐에 삽입되기 때문이다. 그래서 중복을 포함한 모든 정점이우선순위 큐에 삽입 및 삭제에 ElogE가 필요합니다.  

private static int[] dijkstra(Graph graph, int N, int start){
        int[] dis = new int[N+1];
        //다익스트라 알고리즘의 스패닝 트리 (각 노드는 어디 노드에서 왔는지)
        int[] parent = new int[N+1];
 
        Arrays.fill(dis, Integer.MAX_VALUE);
 
        PriorityQueue<Node> pqueue = new PriorityQueue<>();
        dis[start] = 0;
        parent[start] = start;
        pqueue.add(new Node(start, 0));
 
        //E * logE + E
        while (!pqueue.isEmpty()) {
            Node current = pqueue.poll();
 
            //현재 여기를 오는데 쓴 비용이 지금까지 알고 있는 짧은 경로보다 더 클 경우 무시
            if (current.weight > dis[current.v])
                continue;
 
            for (Node nextNode : graph.sparseList.get(current.v)) {
                int newDis = current.weight + nextNode.weight;
 
                if (dis[nextNode.v] > newDis) {
                    dis[nextNode.v] = newDis;
                    pqueue.add(new Node(nextNode.v, newDis));
 
                    //스패닝 트리에 기록, v정점은 현재의 정점 u에서 왔다라는 의미
                    parent[nextNode.v] = current.v;
                }
            }
        }
 
        System.out.println(Arrays.toString(parent));
        return dis;
    }

#2. 우선순위 큐를 사용하지 않는 다익스트라 알고리즘 코드

방문할 정점을 별도의 우선순위 큐에 보관하는 대신 반복문을 이용해 방문하지 않은 정점 중 distance가 가장 작은 정점을 찾는 것으로 대신합니다.

이 코드의 경우 시간복잡도는 V^2 + E가 될것입니다. E는 모든 간선을 방문, V^2은 모든 정점에 대해 distance가 가장 작은 정점을 찾기 위해 V만큼 한번 더 순회하기 때문입니다. (정점의 개수가 적고, 간선의 개수가 매우 많다면 이 방식이 더 빠를 수도 있습니다)

 

# 다익스트라 알고리즘의 스패닝 트리

BFS알고리즘에서 시작점에서 목적지까지의 방문 과정을 찾기 위해 스패닝 트리를 구성하듯, 다익스트라 알고리즘에서도 마찬가지의 방법으로 할 수 있습니다. parent라는 배열을 새로 만들고, u라는 정점에서 v를 방문하면 parent[v] = u라고 기록해두면 됩니다. 소스코드에서 단 두줄만으로 해결이 가능한데, 위 코드의 parent 배열을 생성하는 부분과 인접한 최단 경로를 방문할 때 parent[nextNode.v] = current.v 이 것이면 충분합니다. 

스패닝 트리를 통해 최단 경로를 가져오는 것은 아래 코드를 참고하세요

private static void findRoot(int v, int start, int[] parent) {
        int finish = v;
        StringBuilder sb = new StringBuilder();
        while (v != start) {
            sb.insert(0, " -> "+v);
            v = parent[v];
        }
        sb.insert(0, start);
 
        System.out.println(finish +" : "+sb.toString());
    }

# 증명

귀류법을 사용해 증명하겠습니다. 다익스트라 알고리즘이 제대로 계산하지 못하는 정점 u가 있다고 가정합니다. 다익스트라 알고리즘이 계산한 답은 distance[u], 실제 최단 경로는 distance[q]를 거쳐 u로 가는 경로라 가정할 수 있습니다. 

먼저 u는 시작점이 항상 아니란걸 알 수 있습니다. 왜냐하면 다익스트라 알고리즘은 항상 정확하게 시작점에서의 최단거리를 계산할 수 있기 때문입니다.

다익스트라 알고리즘이 u를 방문하는 순간, u이전에 방문한 정점과 아직 방문하지 못한 정점이 있을 것입니다. 이때 u에서의 최단경로를 계산하지 못했다면 다익스트라 알고리즘이 만드는 스패닝트리의 경로보다 더 짧은 경로가 있다는 것입니다. 그 경로를 q를 통해 u로 가는 경로라고 하고, q 이전에 방문한 정점을 p라고 하겠습니다. 이 때 시작점에서 q까지의 최단경로는 distance[q] + p에서 q로 가는 가중치가 될 것입니다. 하지만 p는 이미 방문한 상태이기에 distance[q]도 이미 값이 있을 것이고, 우선순위 큐에도 그 값이 들어가 있을 것입니다. 그러나 다익스트라 알고리즘에서 우선순위 큐를 사용해 가중치가 가장 작은 값을 찾을 것이고 그것이 u라는 것은 즉, distance[u] < distance[q]를 의미합니다. 즉, q를 지나서 u로 가는 경로가 있다는 말은 모순이 되어 다익스트라 알고리즘의 스패닝 트리보다 더 짧은 경로는 있을 수 없습니다.