최단경로 알고리즘

1. 최단 경로

특정 지점 까지 가장 빠르게 도달하는 방법을 찾는 알고리즘

가. 코딩테스트 문제에서 사용할 때

• 흔히 말하는 '길찾기' 문제에서 사용된다.
• 한 지점에서, 다른 특정 지점 까지의 최단 경로를 구해야 하는 경우. - 또는 모든 지점에서, 다른 모든 지점 까지의 최단경로를 구해야 하는 경우

나. 푸는 방법

• 일반적으로, 그래프를 이용해서 푼다.
• 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로를 찾아야 한다.
• 다익스트라 / 플로이드 워셜 / 벨만포드 알고리즘 3가지가 있다.

다. 하나의 시작 정점에서 끝 정점까지의 최단 경로

• 다익스트라 알고리즘 : 음의 가중치 허용하지 않음
• 벨만-포드 알고리즘 : 음의 가중치 허용

라. 모든 정점들에 대한 최단경로

• 플로이드-워샬 알고리즘

2. 다익스트라 알고리즘

여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 이다.

• 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단경로를 구하는 방식이다.
• 탐욕기법 / 프림알고리즘과 유사하다.
• 간선 가중치가 모두 양수임을 전제로 한다. 그래서 이미 선택된 것은 제외할 수 있다.

가. 조건

음의 간선이 없을 경우에만 사용가능하다.

나. 설명

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화 한다.
3. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다.
4. 해당노드를 거쳐 다른 노드로 가능 비용을 계산하여 최단거리 테이블을 갱신한다.
5. 3,4를 반복한다.

다. 특징

• 최단경로를 구하는 과정에서, 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원리스트에 저장하며, 리스트를 계속 갱신한다.
• 매번 현재 처리하고 있는 노드를 기준으로 간선을 확인한다.
• 기본적으로 그리디 알고리즘이다.
• 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해한다.

라. 알고리즘

Dijkstra(Start , A, Distance){
    U = {s};
    For 모든 정점 V
        Distance[V]  <= A[Start][V]
    
    while U != V
        Distance[W] 가 최소인 정점 W (V-U) 선택
        U <- U  {W}
        for W에 인접한 모든 미방문 정점 V :
            D[V] <- min( D[V], D[W\ + A[W][V])
}

마. 구현

• 디폴트 코드 참조

0. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택하는데, 출발 노드에서 출발 노드로의 거리는 0으로 보기 때문에 처음에는 출발노드가 선택된다.
1. 1번 노드 (출발노드)를 거쳐서 다른 노드로 가는 비용을 계산한다. 즉, 1번 노드에 연결된 간선을 모두 확인하는 것이다.
2. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다. 그리고 연결된 간선을 확인한다.
3. 기존의 리스트 값과 확인하고 작은 것으로 리스트를 갱신한다.
4. 다른 노드의 간선을비교하면서 리스트를 모두 갱신한다.

바. 구현의 두가지 방법

방법 1. 알고리즘을 그래도 구현하기.

• 시간복잡도 : O(V^2) (V는 노드의 개수)
• 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 고르기 위해, 매 단계마다 리스트의 모든 원소를 확인한다.

방법 2. 힙 구조를 이용해서 구현하기.

• 시간복잡도 : O(ElogV) (V는 노드, E는 간선의 개수)
• 힙(Heap)자료구조를 사용한다.
• 힙은 우선순우 큐를 구현하기 위해 보통 사용한다.

3. 플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야하는 경우에 사용할 수 있는 알고리즘

가. 조건

• 가중치가 음이나 양인 그래프에서 사용할 수 있다.

나. 설명

• 임의의 노드 A에서 B까지 가는데 걸리는 최단거리를 구하기 위해, A와 B사이의 노드인 X에 대해서, A-X의 최단거리와 X-B까지 가는데 걸리는 최단거리를 사용한다.
• 동적 계획법의 한 예이다.

다. 특징

A -> B 최소비용 VS A -> X 비용 + X -> B 비용

을 모두 계산하는 것이다.

다. 알고리즘 및 구현

• dp 라는 최단거리 배열이 있다고 생각하면 다음과 같다.
• 주의할점!! for문 맨처음은 x를 거쳐가는 경우를 생각하자.

// 플루이드 - 워셜
int[][] dp = new int[N][N];

for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
		if (i != j)
        	dp[i][j] = max(최댓값);
		}
}

for (int x = 0; x < N; x++) {
	for (int a = 0; a < N; a++) {
		for (int b = 0; b < N; b++) {
			if (dp[a][x] + dp[x][b] < dp[a][b]) 
				dp[a][b] = dp[a][x] + dp[x][b];
					
		}
	}
}