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

이론 핵심 요약

  • 최단경로 알고리즘

    • 특정 정점(시작정점), 에서 현재 존재하는 나머지 모든 정점에 대한 최단 경로 & 최단 경로의 값(비용)을 구할 수 있음

    • 거리값 음수 지원 않함

    • 방향이 있는 그래프에서사용, 무방향이여도 가능

    • 복잡도 O(ElogV)

      • 기본 이론으로 구현시 시간 복잡도 O(V^2), 최적화시 O(ElogV)
        • V: 정점수, E: 간선수
      • 최적화 방법
        • 우선순위 큐 사용
        • Graph을 인접리스트로 표현
      • 최적화 이유
        • 큐에서 노드를 꺼내는 횟수, 큐의 갱신에 대한 반복이 줄어듬.
        • 그래프에서 노드를 하나씩 확인하는 전체 루프에 대한 반복을 줄임

구현 핵심 요약

Java로 설명한다. 우선순위 큐를 사용한 경우만 설명해 두었다.

필요한 요소
  • 그래프를 표현한 자료구조 (ArrayList)
  • 가중치 기록 테이블 (int dist[]) - 가중치 초기화는 infinity 값으로
  • 경로 기록 테이블 (int path[]) - 경로 초기화는 미방분이라는 값(음수값이 좋음) 으로
  • 우선순위 큐 (PriorityQueue)
  • 큐에서 사용하기위한 Node 클래스
코드
Class Dijkstra {
    ArrayList<ArrayList<Edge>> graph;
    int dist [] = new int[your_node_total_number];
    int path [] = new int[your_node_total_number];
    int INFINITY = Integer.MAX_VALUE;
    int NO_PATH  = -1;

    public Dijkstra () {
        Arrays.fill(this.dist, INFINITY);
        Arrays.fill(this.path, NO_PATH);
    }

    public int[] dijkstra (int start_node_id) {
        // 시작 노드 바로 방문, 누적테이블 갱신
        this.dist[start_node_id] = 0; // INFINITY값을 방문값으로 갱신
        this.path[start_node_id] = start_node_id // 시작 노드는 자기 자신에서 부터 출발

        // 시작 노드 방문했으니, 현재 위치 노드를, 큐에 등록
        PriorityQueue<Node> queue = new PriorityQueue<Node>();
        queue.offer(new Node(start_node_id, this.dist[start_node_id]));

        // 순회 방문, 큐가 비면 종료임
        while(!q.isEmpty()) {
            // 큐에서 노드 하나 꺼내옴, (여기서 이미 우선순위(dist)가 짧은 게 바로 나옴)
            Node node = queue.poll();

            // 큐에서 꺼내온 노드의 거리값이, 누적값보다 크면, 가지치기
            if (node.dist > this.dist[node.id]) {
                continue;
            }

            // 아니면, 현재 노드에서 방문 가능한 모든 노들들 체크함
            // 즉 node.id 에서 간선이 있는 노드들을 체크
            // 여기서는 이해를 편하게 하기위해 Edge클래스 도입, 사실 그냥 Node클래스 써도 무방
            ArrayList<Edge> edges = this.graph.get(node.id); // 현재 노드에서 뻗어있는 edge가져옴
            for(int i = 0; i < edges.size(); i++) { // 연결된 edge수만큼만 반복
                Edge edge = edges.get(i);

                // 목적 노드까지의 현재 누적값 VS 현재 노드의 현재 누적값 + 목적 노드까지의 값 비교
                int currentDistForTarget = this.dist[edge.endNodeId];
                int newDistForTarget = this.dist[node.id] + edge.dist;

                // 더 최적값이 있으면
                if (newDistForTarget < currentDistForTarget) {
                    // 목적 노드까지의 누적 테이블 갱신
                    this.dist[edge.endNodeId] = newDistForTarget;

                    // 경로 갱신
                    // edge.endNodeId을 node.id에서부터 방문 햇다고 기록
                    this.path[edge.endNodeId] = node.id;

                    // 최적값이 있었으니, 해당 노드를 큐에서 넣어서
                    // 해당 노드부터 방문하는 곳을 검사 하도록 시킴
                    q.offer(new Node(edge.endNodeId, newDistForTarget));
                }
            }
        }

        return this.dist;
    }
}

class Node implements Comparable<Node> {
    public int id;
    public int dist;

    Node(int id, int dist) {
        this.id = id;
        this.dist = dist;
    }

    // 우선순위 큐에서 sort할때 사용됨
    @Override
    public int compareTo(Node o) {
        return this.dist <= o.dist ? -1 : 1;
    }

    // debug 하기 편한 용도
    @Override
    public String toString() {
        return "Node [id=" + id + ", dist=" + dist + "]";
    }
}

class Edge {
    public int startNodeId, endNodeId;
    public int dist;

    public Edge(int startNodeId, int endNodeId, int dist) {
        this.startNodeId= startNodeId;
        this.endNodeId= endNodeId;
        this.dist= dist;
    }

    public String toString() {
        return "(" + this.startNodeId+ "->" + this.endNodeId+ ") : [" + this.dist+ "]";
    }
}

참고 문서

results matching ""

    No results matching ""