JAVA 로 다익스트라 구현하기

| 목적

 

      ◦ 다익스트라 알고리즘 Java로 구현하기

 

 

 

| 시작하는 말

 

다익스트라의 개념, 순서가 이해가 안된다면 다익스트라란 무엇인가 이 포스트를 먼저 보고 오면 좋다.

 

 

 

| 초기 설정

 

다익스트라를 만들기에 앞서 변수 두가지를 설정해줘야 한다.

distance변수는 각 노드에 갈 수 있는 최단거리를 저장한다.

visit변수는 해당 노드를 방문 했는지를 체크할 변수다.

 

int distance[] = new int[N]; //최단거리들을 저장할 배열을 만든다.
boolean visit[] = new boolean[N]; //해당노드 방문여부를 체크할 배열을 만든다.

 

 

| 예제 (JAVA)

 

public class Dijkstra {
	private static int n;
	private static int maps[][];
	
	public Dijkstra(int n) {
		this.n = n;
		maps = new int[n][n];	 
	}
	
	public void input(int i, int j, int k) {
		maps[i][j] = k;
        maps[j][i] = k;
	}
	
	public static int[] solution(int s) {
		
		int distance[] = new int[n];
		boolean visit[] = new boolean[n]; //boolean은  초기값 false
		
		for(int i = 0; i < distance.length; i++) // distance 최대값으로 초기화
			distance[i] = Integer.MAX_VALUE;
		
		distance[s] = 0; // 초기시작점 자기자신의 거리는 0이므로 0으로 초기화
		visit[s] = true; // 초기시작점 자기자신은 방문해 있는 상태이므로 true로 초기화
		
		for(int i = 0; i < n; i++) { //첫 연결노드 distance갱신
			if(!visit[i] && maps[s][i] != 0)
				distance[i] = maps[s][i];
		}
		
		for(int a = 0; a < n-1; a++) { //다익스트라의 반복수는 자긴자신을 뺀 n-1이면 된다.
			int min_distance = Integer.MAX_VALUE;
			int min_index = -1;
			
			for(int i = 0; i < n; i++) { // disance들 중 최소값 찾기
				if(!visit[i] && min_distance > distance[i]) {
					min_distance = distance[i];
					min_index = i;
				}
			}
			
			visit[min_index] = true; //최종 min_index로 방문할 것이므로 true로 바꾼다.
			
			for(int i =0; i < n; i++) { //새로 방문한 노드와 연결된 distance 갱신
				if(!visit[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;
	
	}

 

 

 

| 참고자료

 

https://bumbums.tistory.com/4

 

 

나는 다익스트라를 이 개발자의 블로그를 보고 공부했었는데,

이분의 코드를 조금 바꿔 코드를 줄여보았다.

 

참고 개발자 소스 코드 中

for(int i=1;i<n+1;i++){
	if(!visit[i] && distance[i]!=Integer.MAX_VALUE){
		if(distance[i]<min ){
			min=distance[i];
			min_index = i;
		}
	}
}

 

 

내가 수정한 코드

 

for(int i = 0; i < n; i++) {
	if(!visit[i] && min_distance > distance[i]) {
		min_distance = distance[i];
		min_index = i;
	}
}