다익스트라(Dijkstra) 알고리즘 자바로 구현하기

- Dijkstra 알고리즘이란? 

그래프의 출발점으로부터 거리가 최소로 알려진 정점들의 집합 S를 유지하고 가장 최소 경로를 가지는 나머지 점을 차례로 집합 S의 포함시켜 가면서 출발점에서 마지막 점까지의 최소 경로를 구하는 알고리즘입니다. 

 

위의 출발점 1에서 마지막 점 5까지 가는 최소 경로는 50입니다. 

 

필요한 변수

- 각 정점들을 담은 집합 v

- 최소 경로를 가지는 정점의 집합 s

- v에서 s집합의 정점을 뺀 정점을 가지는 집합 v_s

- 각 정점까지 경로를 나타내는 집합 d

- 각 정점이 갈 수 있는 경로를 저장한 집합 c

(각 정점이 도달할 수 없는 경로는 적당히 큰 수로 대체합니다.)

 

핵심

v_s의 정점 중의 최소 거리를 가지는 정점 을 집합 s의 포함시키고 경로 집합 d의 경로 값을 갱신합니다. 

만약, m이라는 정점을 지날 경우 시작점->k 경로값과 시작점->m->k 경로의 값 중 최소값을 d[k]에 저장합니다.

 

출력

모든 작업 완료 후 d[5]값이 시작점에서 마지막점까지 도달하는 경로의 최소값이 됩니다. 

 

코드

 

public static void main(String[] args){

int n = 5; //정점의 개수

 

ArrayList<Integer> s = new ArrayList<Integer>();//최소로 알려진 점들의 집합

int idx = 0;

s.add(idx++, 0);

s.add(idx++, 1);

ArrayList<Integer> v = new ArryaList<Integer>(); //정점들의 집합

for(int i=0; i<=n; i++){

v.add(i, i);

}

ArrayList<Integer> v_s = new ArrayList<Integer>();//v_s

for(Integer i : s){

v.remove(i);

}

v_s.addAll(v);

 

int max = 100000;

int[][] c= {

, , ,

, , 

 

}

int[] d = new int[n+1];

for(int i=2; i<=n; i++){

d[i] = c[1][i];

}

 

while(v_s.size()>0){

Integer mIdx = 0;

Integer min = Integer.MAX_VALUE;

for(Integer j : v_s){

if(d[j]==0)

if(d[j]<min){

min = d[j];

mIdx = j;

}

s.add(idx++, mIdx);

v_s.remove(mIdx);

 

for(Integer j : v_s){

d[j] = Math.min(d[j], d[mIdx]+c[mIdx][j]);

}

}

}

System.out.println(d[n]);

}

 

배열의 크기가 n+1인 이유는 인덱스와 정점을 동일시하기 위해서 입니다. 

s는 시작할 때 시작점 1을 원소로 갖습니다. 

c의 원소값을 지정할 때 적당히 큰 값으로 100,000을 입력하였습니다. 

 

whlie문은 v_s의 정점이 없어질 때까지 반복하며 아래는 그 과정입니다.

 

i) s[1]일 경우 d[2], d[3], d[4], d[5] 중 최소 경로인 정점 2를 선택합니다. 

정점 2에서 각 v_s의 정점인 m까지의 거리를 계산할 때 기존의 d[m]보다 값이 작을 경우 그값을 d[m]값으로 합니다. 

d[m] = Math.min(d[m], d[2]+d[2][m]);

d[m]은 시작점에서 m정점까지의 경로입니다.

d[2]는 시작점으로 부터 2정점까지의 거리를 나타냅니다. 

따라서 d[2] + d[2][m]은 시작점으로 부터 2정점을 지나 m 정점까지의 거리입니다. 

 

i의 과정을 v_s에 저장된 각 정점들이 없어질 때까지 수행이 완료되면 d[5]가 결정됩니다. 

 

이상으로 다익스트라(Dijkstra) 알고리즘 포스팅을 마칩니다. 

 

참고 문헌: DISCRETE MATHEMATICS 이산수학 Express - 7장 그래프 응용, 다익스트라 알고리즘.