최단 경로 알고리즘

최단 경로 알고리즘

최단 경로 알고리즘은 그래프 내의 두 정점 사이에서 가장 짧은 경로(최소 비용 또는 최소 거리를 가진 경로)를 찾는

알고리즘 입니다. 이 알고리즘들은 다양한 상황에서 사용되며, 각 알고리즘은 특정한 그래프 특성(음수 가중치, 방향성)에 따라 적합하게 선택됩니다.

 

이러한 최단 경로 알고리즘에는 크게 네 가지가 있습니다.

1. 다익스트라 알고리즘(Dijkstra's Algorithm)

2. 벨만 포드 알고리즘 (Bellman-Ford Algorithm)

3. 플로이드 위셜 알고리즘(Floys-Warshall Alogorithm)

4. A* 알고리즘 (A-Star Algorithm)

 

 

1.  다익스트라 알고리즘(Dijkstra's Algorithm)

다익스트라 알고리즘은 가중치가 양수인 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 

 

 

   - 시작 지점을 설정하고, 그 정점에서 다른 정점으로의 최단 거리를 갱신합니다.

   - 갱신된 정점 중 가장 작은 비용을 가진 정점을 선택하여, 그 정점을 중심으로 다른 정점들의 거리를 다시 갱신합니다.

   - 이 과정을 모든 정점에 대해 반복하여 최단 경로를 찾는다.

 

적용 조건

   - 가중치가 음수인 간선이 없어야 한다.

   - 그래프가 양수 가중치를 가지는 경우에 적합하다.

 

동작 단계

1. 출발 노드와 도착 노드를 설정한다.

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

3. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다.

4. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 최단 거리 테이블을 업데이트한다

5. 3~4의 과정을 반복한다.

 

최단 거리 테이블은 1차원 배열로 N개 노드까지 오는 데 필요한 최단 거리를 기록한다. N개 크기의 배열을 선언하고 큰 값을 넣어 초기화

 

노드 방문 여부 체크 배열은 방문한 노드인지 아닌지 기록하기 위한 배열로, 크기는 최단거리테이블과 같다. 기본적으로는 False로 초기화하여 방문하지 않았음을 명시한다.

 

구현 방법

 

다익스트라 알고리즘을 구현하는 방법에는 방문하지 않은 노드를 다루는 방식에서 순차탐색을 할것인지

우선순위 큐를 쓸것인지 나뉘어진다.

 

순차 탐색 구현

 

방문하지 않은 노드 중 거리값이 가장 작은 노드를 선택해 다음 탐색 노드로 삼는다. 그 노드를 찾는 방식이 순차 탐색이 된다.

즉 거리 테이블의 앞에서부터 찾아내야 하므로 노드의 개수만큼 순차 탐색을 수행해야 한다. 따라서 노드 개수가 N이라고 할 때 각 노드마다 최소 거리값을 갖는 노드를 선택해야 하는 순차 탐색이 수행되므로 (N-1) x N = O(N^2)의 시간이 걸린다.

우선 순위 큐 구현

순차 탐색을 사용할 경우 노드의 개수에 따라 탐색 시간이 매우 오래 걸릴 수 있다.

이를 개선하기 위해 우선 순우 큐를 도입하기도 한다.

거리 값을 담을 우선순위 큐는 힙으로 구현하고, 만약 최소 힙으로 구현한다면 매번 루트 노드가 최소 거리를 가지는 노드가 된다. 최대 힙을 최소 힙으로 쓰려면 저장되는 값에 - 를 붙여 음수로 만든다.

시간 복잡도는 O(E log n) E : 간선의 개수, n은 정점의 개수) - 우선순위 큐 사용경우 

 

 

2. 벨만 포드 알고리즘 (Bellman-Ford Algorithm)

벨만 포드 알고리즘을 음수 가중치를 가진 그래프에서도 최단 경로를 찾을 수 있는 알고리즘

다익스트라 알고리즘과 달리 음수 가중치가 있는 경우에도 사용할 수 있다.

시간 복잡도는 O(V*E) V 정점의 개수, E 간선의 개수

 

작동 방식

각 정점에서 출발해 모든 간선을 반복적으로 탐색하면서 최단 거리를 갱신

모든 정점에 대해 최대 V-1번 간선의 완화를 수행하여 최단 거리를 계산

음수 사이클(음수 가중치의 무한 경로)이 있는지 체크할 수 있음

 

적용 조건

음수 가중치가 있는 그래프에서도 사용가능

음수 사이클이 존재하지 않는 경우에 최적의 해를 찾는다.

 

코드 구현

 

3. 플로이드-워셜(Floyd-Warshall)알고리즘

 

모든 최단 경로를 구하는 알고리즘으로, 음의 간선도 사용할 수 있다.

방향 그래프와 무방향 그래프 모두에서 작동

구현 방법이 간단하다

DP 동적 계획법 기술에 의거하여 사용

 

1. DP 2차원 배열을 각 정점 사이의 가중치로 초기화 한다. 가중치가 없는 경우 inf로 설정

2. 각 중간 정점 K에 대하여 시작 정점 i와 끝 정점 j의 가능한 모든 조합을 반복문으로 탐색하낟.

3. (현재 거리 > 중간 정점 k를 거친 거리) 이면 DP를 업데이트한다.

4. 그래프의 모든 정점에 대해 2-3단계를 반복한다.

시간 복잡도는 O(N^3)이다.

 

단점

큰 그래프의 경우 속도가 느림

중간 결과를 저장하려면 많은 양의 메모리를 필요로 한다.

가중치의 합이 음수인 사이클을 갖는 그래프에서는 사용불가