자바로 만드는 다익스트라 (dijkstra) 알고리즘

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

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

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

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	1	2	3
distance	oo(무한대)	oo	oo
check	false	false	false

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

node	1	2	3
distance	0	oo	oo
check	true	false	false

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

node	1	2	3
distance	0	2	4
check	true	false	false

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

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

node	1	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	1	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

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

감사합니다.