다익스트라 알고리즘 -1

다익스트라 알고리즘은 무엇이고 어떤 용도로 쓰는가?

가중치가 있는 그래프에서 최단거리를 구할 때 쓴다.

여기서 잠깐!! 무방향 인접 그래프에서 최단거리에 관련된 알고리즘은

다음과 같이 대표적으로 3가지 종류가 있음.

 

1.다익스트라 알고리즘

- 하나의 정점에서 모든 정점까지 최단거리를 다구함 (1 : n)

- 간선의 가중치가 양수일때만 사용가능

​

2.플로이드 알고리즘

-모든 정점에서 모든 정점까지 최단거리를 다구함 ( n : n, 물론 1보다 오래걸림)

​

3.벨만포드 알고리즘

- 하나의 정점에서 모든 정점까지 최단거리를 다 구함 (1 : n)

- 간선의 가중치가 양수,음수 상관없이 사용가능

 

우선,

모오오오든 최단경로문제를 관통하는 키포인트는 이것이다.

정점 x에서 y까지 최단거리로 가려면 그 직전(y-1)까지도 최단거리로 가야한다.

1에서 7까지 가는길 중 최단경로가 1 6 2 3 8 7 이라면

1에서 8까지 가는길 중 최단경로는 1 6 2 3 8 이어야한다. 쌩뚱맞은다른 경로면 말이안됨.

​

그래픈데 사이클이 없는 그래프를 트리 라고 하는데,

다익스트라 알고리즘으로 최단거리 간선들을 그리면 트리모양이됨.

이유. 최단경로는 유일하기 때문에 최단경로 "트리" 라는게 나오는 것.

다익스트라 알고리즘이 하는일은 결국 "최단경로트리" 를 어떻게 구할것이냐 하는 과정인 것이다.

​

그래서 최단경로 트리를 어떻게 만들건데???? 준비물을 알아보자.

​

1. n : 총 노드 수

2. map[n][n] : 인접행렬 map[i][j] = w 일때, 노드 i 와 j 사이에 가중치 w인 간선이 존재한다는 뜻.

연결되있지 않으면 0이며, 가중치가 딱히 없는 그래프면 w를 일정한 아무 상수로 넣으면된다. 보통 1로 넣음.

3. int distance[n] : distance[i] = 시작노드에서 i번째 노드까지가는 최단거리를 저장하는 배열. 동적으로 계속 업데이트될것임.

4. boolen visit[n] : 노드 방문철 할 불린 배열.

​

1단계. distance 배열은 아주큰값(무한대) 로 초기화된 상태다. 최단거리를 모르니까.

2단계. 시작노드(=변수 start 라고하자.) 에 방문체크를 하면서 visit[start]에 0이라고 넣는다. 나 에서 나 까지 최단거리는 0이니까!

3단계. 해당노드 i의 방문체크를 하고(visit[i]=true), 해당노드에 바로 인접해있는 노드들을 돌면서(그중하나의 노드를 y라고하자)

distance[i]+map[i][y] 를 했을때 새로운 최솟값이 나올때만 distance[y] 를 업데이트한다.

4단계. distance 배열을 돌면서 방문처리 안한 애들중 distancde[i] 가 최소가되는 노드 i 를 잡는다.

5단계. 모든노드가 방문철이 될때까지 3,4 단계를 반복한다.

​

즉, 초 간단하게 한번더 압축정리하면

1."출발노드~지금노드" 까지의 확정된 최단거리를 이용해서 "출발노드~지금노드에게 인접해있는 노드" 까지의 최단거리를 업데이트하기

2.지금노드를 방문처리하고 최단거리 배열에서 최솟값을 찾아 해당 노드로 가기.

3.모든정점이 방문철 될때까지 반복하기

​

대~충 감이 이제 잡히쥬? 다시한번 포인트를 압축 요약하면?

출발지에서 지금노드의 인접노드까지의 최단거리

= 출발지에서 지금노드까지의 확정된 최단거리+ 지금노드와 인접노드 사이의 가중치

 

라는것!!! 진짜 이 한문장이 개중요함.(★★★★★★★★)

다익스트라를 관통하는 한줄이란것. 동적계획법은 언제나 이런 느낌이조.ㅎㅎ

그래서 자바코드로는 이렇게 짭니다.

 

import java.util.Scanner;

class Graph{ /* 다익스트라 구현 예제*/
    static int n,m;           
    static int maps[][];
 
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	n = sc.nextInt(); //노드수
    	m = sc.nextInt(); //간선수
        maps = new int[n+1][n+1]; //맵 초기화
        
        for(int i=0; i<m; i++){ //간선정보를 맵에 입력받음
        	input(sc.nextInt()+1, sc.nextInt()+1, 1);
        }
        
        int start_node = sc.nextInt()+1;
        int end_node = sc.nextInt()+1;  
        
        dijkstra(start_node,end_node); //start_node 부터 end_node 까지 최단거리를 구한다.(문제에따라 end_node는 없을수도있음)
        sc.close();
    }
    
    public static void input(int i,int j,int weight){
        maps[i][j] = weight;
        maps[j][i] = weight;
    }
 
    public static void dijkstra(int v,int x){
        int distance[] = new int[n+1];      //최단 거리정보 저장용
        boolean[] check = new boolean[n+1]; //방문 체크용
         
        //distance 배열 초기화
        for(int i=1;i<n+1;i++){
            distance[i] = Integer.MAX_VALUE;
        }
         
        //시작노드에서 시작노드까지는 최단거리 0 확정 및 방문체크
        distance[v] = 0;
        check[v] =true;
         
        //연결노드 distance갱신
        for(int i=1;i<n+1;i++){
            if(!check[i] && maps[v][i] !=0){ // 방문안했고 시작노드로부터 직접 연결되어있는 노드이면 
                distance[i] = maps[v][i];    // 최단거리갱신
            }
        }
         
        for(int a=0;a<n-1;a++){ 
            //원래는 모든 노드가 true될때까지 인데 
            //노드가 n개 있을 때 다익스트라를 위해서 반복수는 n-1번이면 된다.
            //원하지 않으면 각각의 노드가 모두 true인지 확인하는 식으로 구현해도 된다.
            int min = Integer.MAX_VALUE;
            int min_index = -1;
             
            //최소값 찾기
            for(int i=1;i<n+1;i++){
                if(!check[i] && distance[i]!=Integer.MAX_VALUE){ 
                    if(distance[i]<min ){
                        min=distance[i];
                        min_index = i;
                    }
                }
            }
            check[min_index] = true;
            for(int i=1;i<n+1;i++){
                if(!check[i] && maps[min_index][i]!=0){
                    if(distance[i]>distance[min_index]+maps[min_index][i]){
                        distance[i] = distance[min_index]+maps[min_index][i];
                    }
                }
            }
        }
        //결과출력
        System.out.print(distance[x]);
    }
}