Dijkstra 알고리즘

목적

• 다익스트라 알고리즘을 이해하기
• 다익스트라 알고리즘을 Java로 구현하기

 

시작하는 말

티스토리 블로그로 이전하고 처음 포스팅하는 글입니다. 첫 게시글은 전 github.io 블로그에서 가장 클릭 수가 많았던 다익스트라 알고리즘을 옮기려고 한다. (검색어는 '다익스트라 2차원 배열')

 

다익스트라(dijkstra) 알고리즘 이란?  

다익스트라 알고리즘은 최단경로를 탐색하는 알고리즘이다. 구현 방법으로 2차원 배열 또는 힙(Heap)을 이용하여 구현할 수 있으며 각각 O(N^2)와 O(ElogN) 시간복잡도를 가진다.  

다익스트라 알고리즘은 음수 가중치를 가진 그래프에서는 사용할 수 없는 단점이 있는데 이때에는 벨만-포드 알고리즘을 사용해야 합니다.  

 

원리  

1. 모든 가중치를 무한으로 설정한다.

2. 방문하지 않은 노드는 false, 방문한 은 true로 설정한다. 하늘색 원안은 true

3. 시작점에서 연결된 노드 들의 가중치의 값을 변환한다.  

4. 그 중 가장 작은 값의 노드를 방문 한다.    

5. 방문한 곳 에서부터 연결된 노드들의 가중치를 변환한다.  

6. 그 가중치보다 다른 경로로 작은 값을 찾으면 해당 노드의 가중치를 변환하며 방문 처리를 하는 것이다.  

 

2차원 배열로 구현한 예제 (JAVA)  

private static final int MY_LOCATION = 1; //시작점
private static final int DESTINATION = 5; //목적지
private static final int START = 0;       //x
private static final int END = 1;         //y
private static final int DISTANCE = 2;    //가중치

public static int solution(int n, int[][] road) {

    int maps[][] = new int[n+1][n+1];       //Map
    int distance[] = new int[n+1];          //노드들의 가중치
    boolean[] check = new boolean[n+1];     //방문여부

    //모든 가중치 가장 큰 값으로 초기 설정
    for(int i=1; i<n+1; i++) {
      distance[i] = Integer.MAX_VALUE;
    }

	//Map 그리기
    for(int i=0; i <road.length; i++) {
      maps[road[i][START]][road[i][END]] = road[i][DISTANCE];
      maps[road[i][END]][road[i][START]] = road[i][DISTANCE];
  	}

    //시작점 셋팅
    distance[MY_LOCATION] = 0;
    check[MY_LOCATION] = true;

    //시작점에서 연결된 노드 연결
    for(int i=1;i<n+1;i++) {
      if(!check[i] && maps[MY_LOCATION][i] != 0) {//값 0 은 Null 의미
        distance[i] = maps[MY_LOCATION][i];
      }
    }

	//탐색 시작

    for(int t=0; t<n-1; t++) {
      int min_distance = 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_distance) {
          		min_distance = 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];
                 }
             }
         }
      }
      return distance[DESTINATION];
}

 

어디에 적용할까?  

다익스트라 알고리즘은 주로 그래프에서 꼭지점 간의 최단 거리를 구하는 문제에 사용된다.

 

오늘 성장에 도움을 주신 개발자분  

  출처 : https://matice.tistory.com/56

  출처2 : https://bumbums.tistory.com/4

오늘도 감사합니다.