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

다익스트라 알고리즘

• 정점 하나를 시작점으로 하여 나머지 정점들 간의 최단거리를 구하는 알고리즘
• 그래프는 무향이거나 유향이나 대부분 유향인 경우가 많으며, 간선 간의 이동거리가 존재한다.
• 또한 거리값이 음수가 아닐 때만 사용할 수 있다.
• 시간복잡도는 인접리스트로 구현했을 경우 O(ElogV), 인접행렬로 구현했을 경우 O(V^2)가 된다.

 

동작 과정

1. 준비물

int E, V, K   // 간선 수, 정점 수, 시작점

class Node // Comparable<Node> {weight 오름차순 비교}

List<List<Node>> graph

int[] distance // 거리 정보 저장

int[] prev // 최단 거리 경로 저장

boolean[] visited

PriorityQueue<Node> pq

 

2. init()

graph에 v+1개의 ArrayList를 추가한다.

distance = new int[V+1];

prev = new int[V+1];

visited = boolean[V+1];

 

3. dijkstra(int K)

pq = new PriorityQueue<>();

Arrays.fill(distance, INF);

distance[K] = 0;  // 시작점 to 시작점의 거리는 0

pq.add(new Node(K, 0);

while(pq가 빌 때 까지){ 거리 갱신}

 

 

소스코드

 

package algorithm;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
 
public class Dijkstra {
    static int v,e,k;
    static List<List<Node>> graph;
    static int[] distance, prev;
    static boolean[] visited;
    
    static class Node implements Comparable<Node>{
        private int idx;
        private int weight;
        
        public Node(int idx, int weight) {
            this.idx = idx;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    }
    
    static void dijkstra(int k) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        
        Arrays.fill(distance, Integer.MAX_VALUE);
        
        distance[k] = 0;
        pq.add(new Node(k,0));
        
        while(!pq.isEmpty()) {
            int cur = pq.poll().idx;
            
            if(visited[cur]) continue;
            visited[cur] = true;
            
            for (Node node : graph.get(cur)) {
                if (distance[node.idx] > distance[cur] + node.weight) {
                    distance[node.idx] = distance[cur] + node.weight;
                    prev[node.idx] = cur;
                    pq.add(new Node(node.idx, distance[node.idx]));
                }
            }
        }
    }
    
    static void input(int v) {
        for(int i = 0; i<=v; i++) {
            graph.add(new ArrayList<>());
        }
        graph.get(1).add(new Node(2,3));
        graph.get(1).add(new Node(5,4));
        graph.get(1).add(new Node(4,4));
        graph.get(2).add(new Node(3,2));
        graph.get(3).add(new Node(4,1));
        graph.get(4).add(new Node(5,2));
        graph.get(5).add(new Node(6,4));
        graph.get(4).add(new Node(7,6));
        graph.get(7).add(new Node(6,3));
        graph.get(3).add(new Node(8,3));
        graph.get(6).add(new Node(8,2));
    }
    
    public static void main(String[] args) {
        v = 8; k = 1;
        graph = new ArrayList<List<Node>>();
        distance = new int[v+1];
        prev = new int[v+1];
        visited = new boolean[v+1];
        input(v);
        dijkstra(k);
        
        for(int i = 1; i<distance.length; i++) {
            System.out.print(distance[i] + " ");
        }
        System.out.println();
        for(int i = 1; i<distance.length; i++) {
            System.out.print(prev[i] + " ");
        }
    }
    
}
 

 

 

참고 사이트

http://blog.naver.com/kks227/220796029558

https://bumbums.tistory.com/4