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

최단 경로(Shortest Path)

최단 경로(Shortest Path)는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 길 찾기 문제라고도 불린다.

아래 세 개의 알고리즘이 주로 사용된다.

• 다익스트라 알고리즘(Dijkstra Algorithm)
• 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)
• 벨만 포드 알고리즘(Bellman-Ford's algorithm)

최단 경로 문제의 특징은 다음과 같다.

• 도로, 길찾기 문제
• 도로(길)와 가중치(값, 시간 등)가 주어지는 경우
  • Ex. A 위치에서 K 를 거쳐 X 로 도착하려고하는 경우에는 플로이드 워셜 알고리즘 사용. (즉, 어디를 거쳐간다고하면 플로이드 워셜 알고리즘일 가능성이 높음)

최단 경로의 문제는 대부분 가중치 방향 그래프가 주어진다.

위 그림 처럼 문제의 요구 사항을 가중치와 방향으로 나타낼 수있다면 최단 경로 문제일 가능성이 높다. 가중지 방향 그래프를 갖는 문제는 메모리에 객체(Node)를 저장해야 한다.

문제에서 도시가 주어지고, 도시는 서로 도로로 연결되어있으며, 도로마다 이동하는데 걸리는 시간이 다르다고하면 만들어야 하는 객체의 형태는 다음과 같다.

class City {

    private int vertex; // 정점
    private int cost; // 비용 : 걸리는시간

    public City(int vertex, int cost) {
        this.vertex = vertex;
        this.cost = cost;
    }

    public int getVertex() {
        return vertex;
    }

    public int getCost() {
        return cost;
    }
}

여기서 City 명을 Node라고 해도 상관없다. 즉,정점(vertext)과 간선 or 비용 or 거리(edge, distance, cost 등)을 속성으로 갖는 노드 객체를 만들어서 문제를 해결한다.

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

다익스트라 알고리즘은 최단 경로(Shortest Path) 문제를 풀기 위한 알고리즘으로 주로 사용된다. 다익스트라는 음의 간선(0보다 작은 값을 가지는 간선)이 없을때 정상적으로 동작한다. 또한 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘으로 분류된다.

다익스트라 알고리즘을 구현하는 방법에는 단순하게 반복문만 사용하여 O(V^2) (V 는 노드의 개수)의 시간 복잡도를 갖게 구현하는 방법이 있으며, 힙(Heap) 자료구조를 사용하는 우선 순위 큐(PriorityQueue)를 사용하여 O(ElogV) (E : 간선의 개수, V : 노드의 개수)의 시간 복잡도를 갖도로 구현할 수 있다.

여기서는 우선 순위 큐(PriorityQueue)를 사용하는 다익스트라 알고리즘 구현 방법에 대해서만 다룰 것이고, 실제로 다익스트라 알고리즘에 관한 대부분의 문제는 우선 순위 큐(PriorityQueue)를 사용한다고 한다.

우선순위 큐는 현재 가장 가까운 노드를 저장하기 위한 목적으로만 이용한다.

// 다익스트라 알고리즘은 가중치 방향그래프(방향과 가중치)가 주어지므로 객체로 만들어서 처리
class Node implements Comparable<Node> {

    private int vertex; // 정점
    private int cost; // 비용

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

    public int getVertex() {
        return vertex;
    }

    public int getCost() {
        return cost;
    }

    @Override
    public int compareTo(Node o) {
        return this.cost - o.cost; // 비용이 낮을 수록 높은 우선순위를 갖도록한다. : 오름차순
    }
}

// 개선된 다익스트라 알고리즘 : PriorityQueue 사용
// PriorityQueue 는 우선순위에 따라 큐에서 뽑아낸다. (우선순위가 가장 높은 데이터를 가장 먼저 삭제한다.)
// 우선순위가 높다는 기준이 필요하기 때문에 Node 객체에 Comparable 을 구현한다.
public class Main {

    private static int INF = Integer.MAX_VALUE;
    private static int n; // 노드의 개수
    private static int m; // 간선의 개수
    private static int start; // 시작 노드 번호

    // 이중 List 인 이유는 가장 바깥 리스트는 각 노드에 대한 리스트이고
    // 내부 리스트는 각 노드에 연결 되어있는 노드들에 대한 정보를 담고 있는 리스트를 의미한다.
    // 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
    // 인접 리스트 방식(Adjacency List) 
    private static List<List<Node>> graph = new ArrayList<>();

    // 최단 거리 테이블 만들기
    private static int[] shortestPaths = new int[100001]; // 노드의 개수는 최대 100000 이라 가정

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        start = sc.nextInt();

        // 그래프 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 모든 간선 정보를 입력받기
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            // a번 노드에서 b번 노드로 가는 비용이 c라는 의미
            graph.get(a).add(new Node(b, c));
        }

        // 최단 거리 테이블을 모두 무한으로 초기화
        Arrays.fill(shortestPaths, INF);

        // 다익스트라 알고리즘을 수행
        dijkstra(start);

        // 모든 노드로 가기 위한 최단 거리를 출력
        for (int i = 1; i <= n; i++) {
            // 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
            if (shortestPaths[i] == INF) {
                System.out.println("INFINITY");
            }
            // 도달할 수 있는 경우 거리를 출력
            else {
                System.out.println(shortestPaths[i]);
            }
        }
    }


    private static void dijkstra(int start) {
        PriorityQueue<Node> pQ = new PriorityQueue<>();
        pQ.offer(new Node(start, 0)); // 자기 자신에 대한 비용은 0
        shortestPaths[start] = 0;

        while(!pQ.isEmpty()) { // 큐가 비어있지 않으면
            Node node = pQ.poll(); // 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
            int nowCost = node.getCost(); // 현재 노드까지 이동하기위한 비용
            int now = node.getVertex(); // 현재 노드(정점)
            if(shortestPaths[now] < nowCost) { // 현재 노드에 대한 최단거리 비용이 더 작은경우 : 즉, 처리된 적이 있는 경우
                continue;
            }
            for (int i = 0; i < graph.get(now).size(); i++) {
                int cost = shortestPaths[now] + graph.get(now).get(i).getCost();
                // 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
                if (cost < shortestPaths[graph.get(now).get(i).getVertex()]) {
                    shortestPaths[graph.get(now).get(i).getVertex()] = cost;
                    pQ.offer(new Node(graph.get(now).get(i).getVertex(), cost));
                }
            }
        }
    }
}

대부분의 다익스트라 알고리즘 문제의 풀이 형태는 구현소스와 크게 다르지 않다.

문제

위 가중치 방향 그래프에서 1번 정점에서 모든 정점으로의 최소 거리 비용을 출력하는 프로그램을 작성하라. 경로가 없으면 Impossible 을 출력.

class Node implements Comparable<Node> {

    public int vertex; 
    public int cost; 

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

    public int getVertex() {
        return vertex;
    }

    public int getCost() {
        return cost;
    }

    @Override
    public int compareTo(Node o){
        return this.cost-o.cost;
    }
}

class Main {

    private static int n;
    private static int m;
    private static List<List<Node>> graph;
    private static int[] shortestPaths;

    public static void main(String[] args){
        input();
        dijkstra(1);
        output();
    }

    private static void input() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        shortestPaths = new int[n + 1];
        Arrays.fill(shortestPaths, Integer.MAX_VALUE);

        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            // a 에서 b 로 가는데 c 의 비용이 든다.
            graph.get(a).add(new Node(b, c));
        }
    }

    private static void dijkstra(int vertex){
        PriorityQueue<Node> pQ = new PriorityQueue<>();
        pQ.offer(new Node(vertex, 0));
        shortestPaths[vertex] = 0; // 자기 자신에 대한 최단거리는 0

        while(!pQ.isEmpty()){
            Node tmp = pQ.poll();
            int now = tmp.vertex;
            int nowCost = tmp.cost;
            if (nowCost > shortestPaths[now]) {
                continue;
            }
            for (Node node : graph.get(now)) {
                if (shortestPaths[node.getVertex()] > nowCost + node.getCost()) {
                    shortestPaths[node.getVertex()] = nowCost + node.getCost();
                    pQ.offer(new Node(node.getVertex(), nowCost + node.getCost()));
                }
            }
        }
    }

    private static void output() {
        for (int i = 2; i <= n; i++) {
            if (shortestPaths[i] != Integer.MAX_VALUE) System.out.println(i + " : " + shortestPaths[i]);
            else System.out.println(i + " : impossible");
        }
    }
}

• shortestPaths[i] : 문제에서 1번 정점에서 시작하니까, 1번 정점에서 i 번째 정점까지 가는데 최소비용을 저장하겠다라는 의미이다.

풀이에서 shortestPaths 가 사진에 나와있는 distances 리스트를 의미한다.보통 다익스트라 알고리즘 문제는 PriorityQueue 를 사용하여 속도를 개선하기 때문에 문제 풀이에서 PriorityQueue 를 사용하였다.

References

• 이것이 코딩 테스트다
• 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비