최단 경로 알고리즘 - 다익스트라

최단 경로 알고리즘이란?

• 가중 그래프 상의 두 노드를 연결하는 가장 짧은 경로를 찾는 방법
• 지도 경로 탐색, 네트워크 구축에 드는 비용을 최소화 하는데 사용
• 최단 경로 알고리즘 종류
  • 다익스트라
  • 벨만-포드
  • 플로이드-워셜

 

다익스트라 알고리즘 (Dijkstra Algorithm)

• 출발점에서 목표점까지의 최단 경로를 구하는 알고리즘
• 한 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있음
• 간선에 음의 가중치가 없어야 함.
  • 하나라도 음의 가중치가 있다면 다익스트라 알고리즘을 사용할 수 없다.
• 그리디 + DP 형태
• 알고리즘 복잡도 : O(ElogV)     * E = Edge , V = Vertex

 

다익스트라 알고리즘 흐름

1. 출발점으로부터의 최단경로를 저장할 노드만큼의 크기를 가진 배열을 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값을 채워 넣는다.

출처 : zero-base

 

 

2. 시작 노드를 기준으로, 시작 노드로부터 갈 수 있는 이웃 노드들의 가중치를 배열에 업데이트한다.

• 시작노드를 A로 했을 때, A 자기자신의 가중치는 0으로 하고 이웃노드들(B,C,E)의 가중치를 최단경로 배열에 업데이트한다.

 

 

 

3. 업데이트한 배열에서 방문하지 않는 가장 최소값의 가중치를 가진 노드로 이동하고, 이동한 노드가 가지고 있는 가중치 + 이웃노드로 이동하기 위한 가중치를 더한 후, 기존 배열에 있던 가중치값들과 비교 후 작은 값을 업데이트한다.

• 최소값부터 노드를 돌기 때문에 그리디이면서 배열을 통해 가중치를 기록하기 때문에 DP이기도 하다.
• 가장 작은 가중치를 가진 B로 이동한 후 , 이웃노드(이미 방문한 A를 제외한 나머지 C,D,F)의 가중치와 B가 가지고 있는 가중치를 더한다. 예를 들어 C의 경우 2(B의 가중치) + 2(B에서 C로이동하는 가중치) = 4인데 기존 C가 가지고 있던 6(A에서 C로 이동하는 가중치)보다 작아 4로 업데이트 해주어야 한다.
• d[B] + P[B][C]의 값이 더 작다면, 즉 더 짧은 경로라면, d[C]의 값을 이 값으로 갱신시킨다

4. 3번을 계속 반복한다

• 가장 작은 D로 이동

• 가장 작은 C로 이동

• 가장 작은 E로 이동

• F,G는 위와 동일하니 생략하겠습니다.

 

5. 시작노드를 기준으로 최단경로 완성

 

 

다익스트라 알고리즘 구현 및 요약

무방향 그래프로 구현 (단방향은 그래프 구성 시에 한쪽만 넣으면 됩니다.)

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 다익스트라 알고리즘 (P[A][B]는 A와 B 사이의 거리라고 가정한다)
 * 1. 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다.
 * 2. 현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장한다.
 * 3. A로부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B]와 d[B]의 값을 비교한다.
 * 4. 만약 d[A] + P[A][B]의 값이 더 작다면, 즉 더 짧은 경로라면, d[B]의 값을 이 값으로 갱신시킨다.
 * 5. A의 모든 이웃 노드 B에 대해 이 작업을 수행한다.
 * 6. A의 상태를 "방문 완료"로 바꾼다. 그러면 이제 더 이상 A는 사용하지 않는다.
 * 7. "미방문" 상태인 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 노드 하나를 골라서 그 노드를 A에 저장한다.
 * 8. 도착 노드가 "방문 완료" 상태가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7의 과정을 반복한다.
 * 9. 이 작업을 마친 뒤, 도착 노드에 저장된 값이 바로 A로부터의 최단 거리이다. 만약 이 값이 INF라면, 중간에 길이 끊긴 것임을 의미한다.
 */

public class Dijkstra {
    static class Node{
        int to;
        int weight;

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

    // 기본 구현 방법
    public static void dijkstra1(int v, int[][] data, int start) {
        ArrayList<ArrayList<Node>> graph = new ArrayList<>();

        // 그래프 작성
        // 0번 인덱스는 사용 X
        for (int i = 0; i < v+1 ; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < data.length; i++) {
            // 그래프를 구성할 때 단방향이면 한쪽 만 그래프에 추가.
            graph.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
            // 양방향이면 양쪽 다 그래프에 추가.
            graph.get(data[i][1]).add(new Node(data[i][0], data[i][2]));
        }

        // 1번 수행
        // 최단경로 저장할 배열 생성
        int[] dist = new int[v + 1];

        for (int i = 0; i < v + 1; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        // 2번 수행
        // 시작점의 최단경로를 0으로
        dist[start] = 0;
        int curIdx = start;

        boolean[] visited = new boolean[v + 1];

        for (int i = 0; i < v; i++) {
            // 3번 ,4번,5번 수행 (인접노드들 가중치 비교)
            for (int j = 0; j < graph.get(curIdx).size(); j++) {
                Node adjNode = graph.get(curIdx).get(j);

               if (dist[adjNode.to] > dist[curIdx] + adjNode.weight) {
                    dist[adjNode.to] = dist[curIdx] + adjNode.weight;
                }
            }
            // 6번 수행 (방문 표시)
            visited[curIdx] = true;

            int minDist = Integer.MAX_VALUE;
            // 7번 수행
            // 방문한 적이 없는 가중치가 가장 작은 노드가 걸러져서 나온다. (다음 노드 찾기)
            for (int j = 1; j < v+1; j++) {
                if (!visited[j] && dist[j] < minDist) {
                    minDist = dist[j];
                    curIdx = j;
                }
            }
        }

        for (int i = 1; i < v + 1; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                System.out.println("INF");
            } else {
                System.out.print(dist[i] + " ");
            }
        }
    }

    // 우선 순위 큐 이용
    public static void dijkstra2(int v, int[][] data, int start) {
        ArrayList<ArrayList<Node>> graph = new ArrayList<>();

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

        for (int i = 0; i < data.length; i++) {
            graph.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
            graph.get(data[i][1]).add(new Node(data[i][0], data[i][2]));
        }

        int[] dist = new int[v + 1];

        for (int i = 0; i < v + 1; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        dist[start] = 0;

        PriorityQueue<Node> queue = new PriorityQueue<Node>(Comparator.comparingInt(node->node.weight));
        queue.offer(new Node(start, 0));

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

            if (dist[curNode.to] < curNode.weight) {
                continue;
            }

            for (int i = 0; i < graph.get(curNode.to).size(); i++) {
                Node adjNode = graph.get(curNode.to).get(i);

                if (dist[adjNode.to] > curNode.weight + adjNode.weight) {
                    dist[adjNode.to] = curNode.weight + adjNode.weight;
                    queue.offer(new Node(adjNode.to, dist[adjNode.to]));
                }
            }

        }

        for (int i = 1; i < v + 1; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                System.out.println("INF");
            } else {
                System.out.print(dist[i] + " ");
            }
        }
    }

    public static void main(String[] args) {
        int[][] data = {{1, 2, 2}, {1, 3, 3}, {2, 3, 4}, {2, 4, 5}, {3, 4, 6}, {5, 1, 1}};
        dijkstra1(5, data, 1);
        System.out.println();
        System.out.println("===============");
        dijkstra2(5, data, 1);
    }
}

References

https://zero-base.co.kr/