Dijkstra (다익스트라)

DP(다이나믹 프로그래밍)를 활용한 대표적인 최단 경로 탐색 알고리즘이다. 하나의 정점에서 다른 모든 정점까지의 최단거리를 구하는 문제에서 사용된다. 최단 거리는 여러 가지 최단 거리로 이루어져 있기 때문에 작은 문제가 큰 문제의 부분 집합에 속해있다고 볼 수 있다. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용하는 특징이 있다. 

 

🕹️ 다익스트라 알고리즘 과정 

1. 출발 노드 설정
2. 출발 노드를 기준으로 각 노드의 최소 비용 저장
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택
4. 해당 노드 거쳐서 특정한 노드로 가는 경우 고려하여 최소 비용 갱신 
5. 3️⃣, 4️⃣번 반복

 

 

 

기본적인 다익스트라 - 선형탐색 

 

public class Main{

	static int INF = 1000000000; // 약 10억
    static int N = 6;

    // 전체 그래프 초기화 
    static int graph[6][6]={0,2,5,1,INF,INF},
                    {2,0,3,2,INF,INF},
                    {5,3,0,3,1,5},
                    {1,2,3,0,1,INF},
                    {INF,INF,1,1,0,2},
                    {INF,INF,5,INF,2,0}};

    static boolean visit[6]; // 방문한 노드
    static int d[6]; // 최단 거리 
    
    public static void main(String[] args){
    	dijkstra(0);
        
        for(int i=0; i<N; i++){
        	System.out.print("%d ", d[i]);
        }
    }
    
    
    // 가장 최소 거리를 가지는 정점 반환
   	static int getSmallIndex(){
    	int min = INF;
        int index=0;
        for(int i=0; i<N; i++){
        	if(d[i]<min && !visit[i]){
            	min = d[i];
                index = i;
            }
        }
        return index;
    }
    
    // 다익스트라 수행하는 함수
    static void dijkstra(int start){
    
    	for(int i=0; i<N; i++){
        	d[i] = graph[start][i];
        }
        
        visit[start] = true;
        
        for(int i=0; i<N-2; i++){
        	int current = getSmallIndex();
            visit[current]=true;
            
            for(int j=0; j<N; j++){
            	if(!visit[j]){
                	if(d[current]+graph[current][j] < d[j]){
                    	d[j] = d[current]+graph[current][j];
                    }
                }
            }
        }
    }
}

➡️ 정점의 개수가 많은데 간선은 적을 때 비효율적으로 작동하므로 권장 X

 

 

 

다익스트라 - 우선순위 큐 

/**
 * 다익스트라 기본 문제
 */
public class BOJ_1753_최단경로 {

    static int V, E, K;
    static ArrayList<Node>[] arr;
    static int[] d;
    static boolean[] visit;
    static int INF = 100;

    static class Node implements Comparable<Node>{
        int v, w;

        public Node(int v, int w) {
            this.v = v;
            this.w = w;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.w, o.w);
        }
    }

    static void dijkstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        d[start] = 0;

        while (!pq.isEmpty()) {

            Node now = pq.poll();

            if (!visit[now.v]) {
                visit[now.v] = true;
            }

            for(int i=0; i<arr[now.v].size(); i++){
                Node next = arr[now.v].get(i);

                if (!visit[next.v] && d[next.v] > now.w + next.w) {
                    d[next.v] = now.w + next.w;
                    pq.add(new Node(next.v, d[next.v]));
                }
            }
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(br.readLine());

        arr = new ArrayList[V + 1];
        d = new int[V + 1];
        visit = new boolean[V + 1];
        Arrays.fill(d, INF);


        for(int i=1; i<=V; i++){
            arr[i] = new ArrayList<>();
        }

        for(int i=1; i<=E; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            arr[u].add(new Node(v, w));
        }

        dijkstra(K);

        for (int i = 1; i <=V; i++) {
            System.out.println(d[i] == 100 ? "INF" : d[i]);
        }
    }
}