[알고리즘] 왜 내 다익스트라 알고리즘은 무겁고 느렸는가?(최적 상태 검사 로직의 위치)

 

 

다익스트라 알고리즘 플로우 요약

 

반복문 이전

1. 출발 노드에서 각 노드로의 최단 거리를 갱신,기록하는 배열 선언
2. 더 적은 이동거리를 우선하는 우선순위 큐를 선언
3. 우선순위 큐에 초기 상태 삽입

반복문 이후

1. 큐에서 꺼낸 상태가 현재 최소 경로인지 검사 및 갱신
2. 다음 방문 가능한 노드에 대하여 큐에 삽입

 

 

다익스트라의 꽃은 최적 상태 검사

 

다익스트라 알고리즘은 출발 노드로 부터 각 모든 도착 노드까지 최소 비용의 경로로 방문하게 되는 알고리즘이다.

따라서 최적으로 이동하고있지 않은 상태는 유망하지 않은 상태가 되며 더 이상 탐색하지 않아도 된다.

예를 들어 a 노드에서 c 노드까지 가는데 이미 5라는 비용으로 방문하는 방법을 알았다면, 7이라는 비용이 발생하는 동일 경로는 버려버리면 된다.

이 때 현재 상태가 최적의 상태인지 검사하는 로직이 필요한데, 이 로직이 큐에 삽입하기 이전인지 이후인지가 메모리와 시간 사용에 영향을 끼치게된다.

 

 

습관이 들어 잘못 짜던 코드(일단 큐에 넣기)

 

방문 가능한 노드는 모두 큐에 넣고나서 나중에 큐에서 뽑아서 유효한노드인지 검사하면 시간+메모리를 아주 조금 많이 씀 (queue에 많이 들어가고 나오니까)

// 필요한 자료구조 선언
int[] minDist = new int[n+1];
Arrays.fill(minDist, Integer.MAX_VALUE);
PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));

// 초기 상태 정의
q.add(new int[]{start, 0});

while(!q.isEmpty()) {
	int[] now = q.poll();
	int pos = now[0];
	int dist = now[1];
    
    // 최소 경로인지 검사 및 갱신
	if(minDist[pos] <= dist)
		continue;
	minDist[pos] = dist;
    
	for (int[] next : edges[pos]) {
   		int nextPos = next[0];
		int nextDist = dist + next[1];
		if(minDist[nextPos] > nextDist){
        
        	// 방문 가능하면 방문 노드에 추가
			q.add(new int[]{nextPos, nextDist});
		}
	}
}

 

 

최소 경로를 미리 갱신하도록 하기(원래 올바른 다익스트라 알고리즘)

 

따라서 Queue에 추가하기 이전에 최적의 경로로 이동중인지 검사하여 맞다면 삽입하는 것이 더 좋다.

• 주의할 것은 탐색 시작 전에 start 노드에 대한 최소 경로를 0으로 초기화 해줘야한다는 것 (start 노드로 이동하는 경우 순환발생 가능)

// 필요한 자료구조 선언
int[] minDist = new int[n+1];
Arrays.fill(minDist, Integer.MAX_VALUE);
PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));

// 초기 상태 정의 및 최소 경로 초기화
q.add(new int[]{start, 0});
minDist[start] = 0;

while(!q.isEmpty()) {
	int[] now = q.poll();
	int pos = now[0];
	int dist = now[1];
    
    
	for (int[] next : edges[pos]) {
    	int nextPos = next[0];
		int nextDist = dist + next[1];
		if(minDist[nextPos] > nextDist){
        	// 방문 가능 노드인 경우 미리 최소경로를 갱신해서 다른 비효율적인 경로를 탐색하지 않도록 함
			minDist[nextPos] = nextDist;
			q.add(new int[]{nextPos, nextDist});
		}
	}
}

 

 

구하는 최소 경로가 1개인 경우 유망하지 않은 노드 제거하는 코드 추가(잡기술)

 

현재 도착 지점에 대한 최소의 경로보다 크거나 같은 state에 대한 탐색을 하지 않는 방법이 있다.

// 필요한 자료구조 선언
int[] minDist = new int[n+1];
Arrays.fill(minDist, Integer.MAX_VALUE);
PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));

// 초기 상태 정의 및 최소 경로 초기화
q.add(new int[]{start, 0});
minDist[start] = 0;

while(!q.isEmpty()) {
	int[] now = q.poll();
	int pos = now[0];
	int dist = now[1];
    
    // 유망하지 않은 노드 탐색 중지
	if(dist >= minDist[end])
		continue;
        
	for (int[] next : edges[pos]) {
		int nextPos = next[0];
		int nextDist = dist + next[1];
		if(minDist[nextPos] > nextDist){
            // 방문 가능 노드인 경우 미리 최소경로를 갱신해서 다른 비효율적인 경로를 탐색하지 않도록 함
			minDist[nextPos] = nextDist;
			q.add(new int[]{nextPos, nextDist});
		}
	}
}