다익스트라 알고리즘

다익스트라 알고리즘

네덜란드 컴퓨터 과학자 에츠허르 다익스트라(Edsger Wybe Dijkstra)가 고안한 알고리즘으로,
그래프의 특정 정점 으로부터 다른 모든 정점 까지의 최단 경로를 구하는데 사용됩니다.

방향그래프 혹은 무방향그래프 둘다 사용할 수 있습니다.

다익스트라 알고리즘은 그리디 알고리즘의 일종으로 매 단계에서 현재까지 알려진 가장 짧은 경로를 선택하여 점진적으로 최적해를 탐색합니다.

동작원리

1. 시작 정점과 인접한 정점들의 거리를 구합니다.

2. 인접한 정점중 가장 가까운 정점을 구합니다.
   이때, 선택된 가장 가까운 정점과 시작 정점과의 거리는 확정됩니다.

3. 시작 정점과 가장 가까운 정점의 거리를 이용하여 다른 정점간의 최단 거리를 구합니다.

4. 2번과 3번을 반복합니다.

쉬운 구현

public class Main{
    static int INF = 100000000;
    static int[] dijkstra(ArrayList<ArrayList<Edge>> graph, int start){
        int len = graph.size();
        boolean[] visited = new boolean[len];
        int[] d = new int[len];
        Arrays.fill(d,INF);
        d[start] = 0;

        for (int i = 0; i < len; i++) {
            int minIndex = findClosestNode(d,visited);
            int cost = d[minIndex]; //시작정점 에서 해당 정점까지의 거리.
            for(Edge edge : graph.get(minIndex)){
                if(d[edge.to] > cost + edge.value){ //최단 거리 갱신
                    d[edge.to] = cost + edge.value;
                }
            }
            visited[minIndex] = true; //방문 처리.
        }
        return d;
    }
    static int findClosestNode(int[] d, boolean[] visited){
        int index = 0;
        int min = INF + 1;
        for (int i = 0; i < d.length; i++) {
            if(!visited[i] && min > d[i]){ //방문하지 않은 정점중 가장 가까운 정점 선택.
                index = i;
                min = d[i];
            }
        }
        return index;
    }
}
class Edge{
    int to;
    int value;

    public Edge(int to, int v) {
        this.to = to;
        this.value = v;
    }
}

위 구현에서 가장 가까운 정점을 찾을때 선형 탐색을 이용하고있다.
그래프의 노드의 개수가 많은 경우 비효율적으로 동작하게 된다.
이때, 우선순위 큐 자료구조를 이용해 코드를 개선할 수 있습니다.

우선순위 큐 사용 구현

public class Main{
    static int INF = 100000000;
    static int[] dijkstra(ArrayList<ArrayList<Edge>> graph, int start){
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.distance));
        int[] d = new int[graph.size()];
        Arrays.fill(d,INF);
        d[start] = 0;
        queue.add(new Node(start,0));
        while(!queue.isEmpty()){
            Node node = queue.poll(); //가장 가까운 정점을 선택.
            int minIndex = node.index;
            if(d[minIndex] < node.distance) continue;

            for(Edge edge : graph.get(minIndex)){
                int cost = d[minIndex] + edge.value;
                if(d[edge.to] > cost){ //최단 거리 갱신
                    d[edge.to] = cost;
                    queue.add(new Node(edge.to, cost));
                }
            }
        }

        return d;
    }
}
class Node{
    int index;
    int distance;

    public Node(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }
}
class Edge{
    int to;
    int value;

    public Edge(int to, int value) {
        this.to = to;
        this.value = value;
    }
}

주의 사항

다익스트라 알고리즘은 음의 가중치가 있는 간선이 그래프에 포함되어 있으면 사용할 수 없습니다.

• 이미 방문한 정점의 거리가 더 짧아질 수 있음
  다익스트라 알고리즘은 한 번 방문한 정점의 거리를 더 이상 변경하지 않습니다. 이는 양의 가중치에서는 괜찮지만, 음의 가중치가 있으면 문제가 됩니다. 예를 들어, 이미 방문한 정점을 거쳐서 더 짧은 경로가 나중에 발견될 수 있는데, 알고리즘은 이를 반영하지 못해요.
• 최단 경로의 특성이 깨짐
  양의 가중치에서는 최단 경로가 보통 더 적은 간선을 사용하는 경로로 나타납니다. 하지만 음의 가중치가 있으면 간선을 더 많이 거치는 경로가 오히려 거리 합계가 더 작아질 수 있어요. 다익스트라 알고리즘은 이런 경우를 처리할 수 없습니다.