[알고리즘] 다익스트라(Dijkstra) 알고리즘

• 최단 경로 : 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로
• 간선의 가중치가 없는 경우(모든 점의 가중치가 똑같다는 의미) : 두 정점 사이의 경로에 쓰인 정점의 개수가 최소

다익스트라(Dijkstra) 알고리즘

• 하나의 시작 정점에서 끝 정점까지의 최단 경로
• 음의 가중치를 허용하지 않음
• 시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식
• 탐욕 기법을 사용한 알고리즘으로 MST의 Prim 알고리즘과 유사함

Pseudo-Code

s : 시작 정점, A : 인접 행렬, D : 시작 정점에서의 거리 (시작 정점에서 자신까지 오는 거리 비용)
v : 정점 집합, U : 선택된 정점 집합

Dijkstra(s,A,D)
	U = {s};
    
    // 최초 한 번
    FOR 모든 정점 v //시작 정점 s에서 모든 정점 v로 가는 비용
    	D[v] ← A[s][v] //시작 정점에서 자신으로 오는 직접 비용 (다른 애들을 안거치고 오는 비용)을 디폴트로 두고 출발
    
    // 반복
    WHILE U != V
    	D[w]가 최소인 정점 w ∈ V-U를 선택 //전체 정점 v에서 선택된 정점 U를 제외하여 선택 (아직 처리하지 않은 정점들)하여 자신으로 오는 비용이 최소인 정점 찾기. 즉, 출발 정점에서 거리가 가장 가까운 애 찾기
        U ← U ∪ {w}
        FOR w에 인접한 모든 미방문 정점 v //이미 처리된 애들은 절대 들여다보지 않음. 이미 처리된 애들은 지금 나의 비용보다 훨씬 유리한 비용임.
        	D[v] ← min(D[v],D[w]+A[w][v]) //기존 단계까지 S->V 최소 비용 D[v]보다 w라는 정점을 거쳐서 v 정점까지 왔을 때의 비용이 더 유리하다면 최소비용 업데이트

JAVA 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class DijkstraTest {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int	V = Integer.parseInt(br.readLine());
		int start = 0;//시작점
		int end = V-1; //도착점
		
		StringTokenizer st =null;
		int[][] adjMatrix = new int[V][V]; 
		
		for(int i=0;i<V;i++) {
			
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<V;j++) {
				adjMatrix[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		
		int[] distance = new int[V];
		boolean[] visited = new boolean[V];
		
		Arrays.fill(distance, Integer.MAX_VALUE);
		distance[start] = 0;
		
		// O(V^2)
		for(int i=0;i<V;i++) {
			int min = Integer.MAX_VALUE; //distance[current]
			int current = 0; //min 최소비용에 해당하는 정점 번호
			
			//step1. 처리하지 않은 정점 중에 출발지에서 가장 가까운(최소비용) 정점 선택
			for(int j=0;j<V;j++) {
				if(!visited[j]&& min>distance[j]) {
					min = distance[j];
					current = j;
				}
			}
			
			visited[current] = true;
			if(current == end) break;
			
			//step2. 선택된 current를 경유지로 하며 아직 처리하지 않은 다른 정점으로의 최소 비용을 따져본다.
			for(int j=0;j<V;j++) {
				if(!visited[j] && adjMatrix[current][j]!=0 && distance[j]>min+adjMatrix[current][j]) {
					distance[j] = min+adjMatrix[current][j]; //distance[current]+adjMatrix[current][j]
				}
			}
			
		}
		
		System.out.println(distance[end]);
		
	}

}

다음에는 Priority Queue를 적용해서 코드를 작성해보자.