[이것이취업을위한코딩테스트다] chap09 - 최단 경로 알고리즘

최단 경로 알고리즘

 

가장 짧은 경로를 찾는 알고리즘으로 다음과 같은 다양한 문제 상황에 쓰인다.

1) 한 지점에서 다른 한 지점까지의 최단 경로

2) 한 지점에서 다른 모든 지점까지의 최단 경로

3) 모든 지점에서 다른 모든 지점까지의 최단 경로

각 지점은 그래프에서 노드로 표현, 연결된 선은 간선으로 표현한다.

 

 

다익스트라 최단 경로 알고리즘

 

특정한 노드에서 출발하여 다른 모든 노드로 가는 최단경로 계산으로, 음의 간선이 없을 때 정상적으로 동작한다. 그리디 알고리즘으로, 매 상황에서 가장 비용이 적은 노드를 선택해 과정을 반복한다.

 

동작 과정

1) 출발 노드를 설정한다.

2) 최단 거리 테이블을 초기화한다.

3) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.

4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

5) 위 과정 3, 4번을 반복한다.

위와 같이 처리 과정에서 더 짧은 경로를 찾으면, 해당 경로로 최단 거리가 갱신되는 구조이다.

 

그래프를 준비하고, 자기 자신 노드는 0, 다른 노드는 무한으로 설정한다.

 

방문하지 않은 노드 중에서, 최단 거리가 가장 짧은 노드 1번을 처리한다. 원래 값인 1의 0과 인접 노드로 가는 간선의 값을 더해, 현재 값과 비교한 후 더 작으면 갱신하고 크면 패스한다.

그 다음 짧은 노드인 4번도 동일한 방식으로 처리한다.

이렇게 가장 짧은 노드를 순차적으로 처리하면서 더 이상 이동할 수 있는 인접 노드가 없을 때까지 반복한다.

 

 

다익스트라 알고리즘 특징

 

그리디 알고리즘처럼 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의 과정을 반복한다. 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 바뀌지 않는다. 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장되고, 최단 경로를 구하려면 소스코드에 추가적인 기능을 넣어야 한다.

 

 

다익스트라 알고리즘의 성능 분석

 

총 O(V)번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 하므로, O(V^2)의 시간 복잡도를 가지고 있다. 하지만 노드가 10,000개가 넘어간다면 우선순위 큐를 활용해 구해야 한다.

 

 

 

우선순위 큐

 

우선순위 큐는 가장 우선순위가 높은 데이터를 가장 먼저 삭제하는 자료구조이다.

 

 

힙

 

힙은 우선순위 큐를 구현하기 위해 사용하는 자료구조로, 최소 힙과 최대 힙이 있다.

 

 

방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙 자료구조를 이용하고, 동작하는 기본 원리는 동일하다.

 

위와 같이 출발 노드를 설정하여 우선순위 큐에 삽입한다. 이 때 거리와 노드를 모두 삽입한다.

 

우선순위 큐에서 해당 원소를 꺼내고, 1번 노드를 아직 방문하지 않았으므로 이를 처리한다.

다음 우선순위인 4번 노드를 처리하고

 

모든 노드를 방문했을 시 작동을 멈춘다.

 

 

개선된 다익스트라 알고리즘의 성능

 

시간 복잡도느는 O(ElogV)이며, E는 최대 간선의 개수이고 V는 노드의 개수이다. E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사하므로

위와 같은 시간복잡도를 유도할 수 있다.

 

 

 

 

플로이드 워셜 알고리즘

 

모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 다이나믹 프로그래밍 유형에 속하고 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다.

즉 위와 같이 a에서 b로 가는 최단거리와, a에서 k를 거쳐 b로 가는 거리를 비교하여 더 짧은 거리로 갱신한다.

그래프를 초기화하고

위와 같이 n번 노드를 거쳐 가는 경우를 고려하면서 테이블을 갱신한다.

 

 

플로이드 워셜 알고리즘 성능

 

노드 개수가 N개일 때, N번의 단계를 수행하므로 O(N^2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다. 즉 총 시간 복잡도는 O(N^3)이다.