티스토리 뷰

다익스트라 알고리즘은 그래프에서 출발점에서 목표점까지의 

최단거리를 구할 때 사용하는 알고리즘 입니다.




다익스트라를 사용할 때 사용하는 변수는 두개가 있습니다.

int distance[] = new int[n+1]; 			//최단 거리를 저장할 변수
boolean[] check = new boolean[n+1];		//해당 노드를 방문했는지 체크할 변수


distance 변수에는 각각의 노드까지의 최단거리가 저장됩니다.

check 변수에는 각각의 노드를 방문했는지를 표시할 예정입니다.



다익스트라 알고리즘의 순서는 이렇습니다.


1. distance는 처음에 나올 수 있는 가장 큰 값으로 초기화 해줍니다.  

여기서는 Integer.MAX_VALUE 값으로 초기화 하겠습니다.

(문제에서 100000만 이상의 값은 안나온다 하면 100001로 초기화 하셔도 됩니다.)


2. 시작노드의 거리를 0 으로 표시합니다(자기자신까지 거리는 0이므로)

   그리고 시작노드의 check값을 true로 바꿔줍니다. (방문 한것이므로)


3. 시작노드와 연결되어 있는 노드들의 distance 값을 갱신합니다.


4. 방문하지 않은 노드중 distance 값이 최소인 노드 min_node를 찾습니다.

5.  min_node의 check 값을 true로 변경합니다.

    그리고 min_node와 연결된 노드들(방문하지 않은) distance 값을 갱신합니다.

    이때 min_node와 연결된 distance 값이 

    distance[min_node] + (min_node와 그 노드의 거리)

    보다 큰 경우 distance값을 distance[min_node] +(min_node와 그 노드의 거리)

    로 갱신해줍니다.


4~5를 모든 노드를 방문할 때까지 반복합니다.




...글로 제가 너무 어렵게 설명해드려서 헷갈리시죠 ㅠ.ㅠ....

과정을 다시 한번 간단한 그림으로 설명해드리겠습니다.


아래와 같은 그래프가 있다고 해보겠습니다.


다음과 같은 그래프가 있습니다. 여기서 시작점을 1로 잡아보고 시작해보겠습니다.

1.distance를 초기화 해줍니다. 


node 

2

3

 distance

oo(무한대)

oo

oo

 check

false 

false

false 


2.시작노드가 1이므로 시작노드의 distance와 check값을 변경해줍니다.


 node

2

3

 distance

0

oo

oo

 check

true

false

false 


3.시작노드와 연결되어 있는 distance값을 갱신합니다.

node 

2

3

 distance

0

2

4

 check

true 

false

false 


4.방문하지 않은 노드중 distance가 최소인 값을 찾습니다. (노드 2)


5.최소인 노드 2의 check값을 true로 변경합니다.


 node

2

3

 distance

0

2

4

 check

true

true

false 


그리고 2랑 연결되면서 방문하지 않은 노드들에 대해서

(여기선 3번노드)

distance(3) > distance(2) + (2번과3번 거리) 이면

distance(3) = distance(2) + (2번과3번 거리) 합니다.

여기서 3번까지의 거리는 현재 4입니다.

이것이 2번까지 거리(2)+ 2와3거리(1) 보다 현재 크므로

distance(3) 에는 3의 값이 들어가게 됩니다. 


 node

2

3

 distance

0

2

3

 check

true

true

false 


위와 같이 노드 3의 distance값은 더 최소인 값으로 갱신되게 됩니다.



이제 맨처음 그림을 가지고 다익스트라 알고리즘구현해보겠습니다.

class Graph{
	private int n;			 //노드들의 수
	private int maps[][]; 	 //노드들간의 가중치 저장할 변수

	public Graph(int n){
		this.n = n;
		maps = new int[n+1][n+1];
		
	}
	public void input(int i,int j,int w){
		maps[i][j] = w;
		maps[j][i] = w;
	}

	public void dijkstra(int v){
		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;
		}
		
		//시작노드값 초기화.
		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];
					}
				}
			}

		}
		
		//결과값 출력
		for(int i=1;i<n+1;i++){
			System.out.print(distance[i]+" ");
		}
		System.out.println("");
		
	}
}


메인함수 부분입니다.

public class Main {

	public static void main(String[] args) {
		Graph g = new Graph(8);
		g.input(1, 2, 3);
		g.input(1, 5, 4);
		g.input(1, 4, 4);
		g.input(2, 3, 2);
		g.input(3, 4, 1);
		g.input(4, 5, 2);
		g.input(5, 6, 4);
		g.input(4, 7, 6);
		g.input(7, 6, 3);
		g.input(3, 8, 3);
		g.input(6, 8, 2);
		g.dijkstra(1);
	}

}

결과값 입니다^^


1번 노드까지 가는 최단거리는 0 

2번 노드까지 가는 최단거리는 3

...

8번 노드까지 가는 최단거리는 8

로 잘 나온 것을 확인할 수 있습니다!!


감사합니다.

댓글
  • 프로필사진 질문이요!~! 이거 혹시 1 인덱싱 코드인가요? 아니면 0 인덱싱 코드인가요?
    0 인덱스 버리고 한건지 아니면 어떤 특별한 이유가 있는 건지
    for문을 0에서 시작안하시고 1에서 시작하셔서 질문드립니다!~!


     for(int i=1;i<n+1;i++){
                distance[i] = Integer.MAX_VALUE;
            }


    2017.05.18 16:41
  • 프로필사진 범범스 안녕하세요^^ 노드번호랑 일치하게하기위해서 0번인덱스를 제외했습니다. 그리고 인풋할때도 노드번호에 해당하는 map값을 바꿨습니다. 2017.05.18 16:45 신고
  • 프로필사진 질문입니다! 안녕하세요 위의 코드 참고삼아 다익스트라로 이것저것 실험해보는 중입니다.
    혹시 최단 경로까지 출력하려면 어떻게 활용하면 될까요?
    8번노드까지 최단 경로 : 1 -> 2 -> 3 -> 8 이런식으로요!
    2018.12.02 18:38
  • 프로필사진 백두산 질문있습니다!
    혹시 for(int i=1;i<n+1;i++) {
    if(!check[i] && line[a][i] !=0){
    distance[i] = line[a][i];
    }
    여기서 if(!check[i] && line[a][i] !=0) 이렇게
    !와!을 사이에 두셨는데 무슨의미인가요? 그리고 && 이렇게 2개를 쓰셨는데 이것이 무엇을 의미하는지 알고싶습니다! 검색해도 안나오네요 ㅜ
    2018.12.28 21:34
  • 프로필사진 빵꾸똥꾸 먼저 !check[i] 는 check배열이 boolean이기 때문에 true or false 값을 가지게 됩니다. 앞에 !를 붙였다는 것은 배열 값의 역을 취한다는 것입니다. true면 false로 false면 true로. 그리고 &&는 A && B 처럼 쓰이게 되는데 A와 B는 조건문입니다. 둘다 true or false 결과가 나오는데 &&는 양쪽 모두 true일 경우를 true로 취하고 한쪽이라고 false인 경우 false로 결과를 냅니다. 그리고 != 는 양쪽이 같지 않은 경우를 나타냅니다. 결론적으로 if( !check[i] && line[i][i] != 0) 의 조건을 해석 해보면 check[i]가 false이고(&&) line[i][i]가 0이 아니면 if문을 실행한다. 연산자는 거의 모든언어가 동일하니까 자세히 보시는걸 추천드릴게용 채택 부탁드립.ㅋㅋㅋㅋ 도움이 되셨길.. 2019.03.27 22:27
  • 프로필사진 ㅁㄴㅇㄹ 아주 깔끔한 코드네요 감사합니다 :) 2019.04.22 17:04
  • 프로필사진 범범스 감사합니다^^ 2019.09.05 00:12 신고
  • 프로필사진 코드만 따라가도 잘 이해됩니다. 좋은 글 감사합니다. bb 2019.05.22 11:40
  • 프로필사진 범범스 감사합니다^^ 2019.09.05 00:12 신고
  • 프로필사진 ㅇㅇㅅ 3노드에서 7노드로 갈 때 최단경로는 구할 수 없나요?ㅜㅜ 2019.11.08 03:07
  • 프로필사진 과객 제가 여지껏 본 다익스트라 알고리즘에 대한 포스팅 중에서 최고입니다. ㅎㅎ 이거 보다 쉽고 정확한 설명은 못봤네요 2020.12.30 18:40
  • 프로필사진 도날두덱 다익스트라알고리즘 조조조 조아용 2021.07.03 04:36 신고
댓글쓰기 폼