최단 경로 알고리즘 (다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘)

 최단 경로(Shortest Path) 알고리즘이란?

---

• 가장 짧은 경로를 찾는 알고리즘, '길 찾기' 문제로 불린다.
• 문제를 그래프로 표현하고 각 지점을 노드, 지점간 연결된 도로는 간선이라 한다.
• 최단 경로 알고리즘에는 그리디 알고리즘과 다이나믹 프로그래밍이 그대로 적용된다.
• 다양한 사례가 존재하며, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다.
  • 문제 형태가 정형화되어 있기 때문에 구현 부분은 비슷함
    문제에 따른 외적인 조건만 챙겨서 풀이
    
    ex) 한 지점에서 다른 특정 지점까지 최단 경로 구하기, 모든 지점에서 다른 모든 지점까지 최단 경로 구하기 등

 

1) 최단 경로 문제의 종류

• 단일 출발 (single-source) 최단 경로
  • 어떤 하나의 정점에서 출발하여 나머지 모든 정점 까지의 최단 경로를 찾는 문제
• 단일 도착 (single-destination) 최단 경로
  • 모든 정점에서 출발하여 어떤 하나의 정점까지의 최단 경로를 찾는 문제로 그래프 내의 간선들을 뒤집으면 단일 출발 최단거리 문제로 바뀔 수 있다.
• 단일 쌍(single-pair) 최단 경로
  • 모든 정점 쌍들 사이의 최단 경로를 찾는 문제

2) 주요 알고리즘

• BFS (완전탐색 알고리즘)
  • 가중치가 없거나 모든 가중치가 동일한 그래프에서 최단경로를 구하는 경우 가장 빠르다
• 다익스트라 알고리즘 (Dijkstra Algorithm)
  • 음이 아닌 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제
• 벨만-포드 알고리즘 (Bellman-Ford-Moore Algorithm)
  • 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제
• 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)
  • 전체 쌍 최단 경로 문제

 

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

1) 다익스트라 알고리즘이란?

V개의 정점과 음수가 아닌 E개의 간선을 가진 그래프 G에서 특정 출발 정점(S)에서 부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘

 

D[S]=0 (자기 자신으로 가는 가중치는 0이므로 출발점을 0으로 저장)

방문하지 않은 정점 중에서 D[K]가 최소인 정점 I 선택

D[J] = D[I] + W 로 갱신

 

특징

• 각 정점을 최대 한 번씩만 방문하여 최단 거리를 확정한다. (음의 가중치를 가질 수 없다, visited 배열을 활용)
• 아직 방문하지 않은 정점들 중 최단거리인 점을 찾아 방문하여 최단거리를 확정하고, 이를 반복하는 방식으로 진행된다.
• 총 V*V번 연산이 필요하다. 따라서 O(V^2)의 시간복잡도를 가진다.
• 방문하지 않은 정점 중에서 최단 거리가 최소인 정점을 찾는 과정에서 우선순위 큐 혹은 힙 자료구조를 이용하면 더욱 개선된 알고리즘이 가능하다.

2) 개선된 알고리즘 단계 (우선 순위 큐 활용)

D[S]=0 (출발점을 0으로 저장) + 최소 힙에 출발점 S 삽입

최소 힙에서 맨 위에 있는 정점 I 꺼냄

D[J] = D[I] + W 로 갱신 + 최소 힙에 정점 J 삽입

 

특징

• 최악의 경우 모든 간선을 확인할 때 마다 거리 배열이 갱신이 된다고 하면, 최소 힙에는 최대 E번 정점을 넣게 된다. (간선의 개수가 E개 이기 때문)
• 최소 힙에 E개의 정점이 있을 때, 하나의 정점을 꺼낼 때 마다 logE의 연산이 필요하다. (최소 힙 삭제연산의 시간복잡도)
• 시간 복잡도 : ElogE = ElogV^2 = 2ElogV
• 즉, 최소 힙 혹은 우선순위 큐를 사용하는 경우, 시간 복잡도는 O(ElogV)이다.

 

 

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

V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 특정 출발 정점(S)에서 부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘이다.

V개의 정점과 E개의 간선을 가진 가중 그래프에서 어떤 정점 A에서 어떤 정점 B까지의 최단거리는 최대 V-1개의 간선을 사용한다. (시작 정점 A를 포함하여 최대 V개의 정점을 지난다.)

 

특징

• 음의 가중치를 가지는 간선도 가능하다.
• 음의 사이클의 존재 여부를 확인할 수 있다.
• 최단거리를 구하기 위해서 V-1번 E개의 모든 간선을 확인한다.
• 음의 사이클 존재 여부를 확인하기 위해서 한 번 더 E개의 간선을 확인한다.
• 총 연산횟수는 V*E이다. 따라서 시간복잡도는 O(VE)이다.
• V번째 모든 간선을 확인하였을 때 거리 배열이 갱신되었다면, 그래프 G는 음의 사이클을 가지는 그래프이다.
  • 그래프 모든 엣지에 대해 edge relaxation을 시작 노드를 제외한 전체 노드 수 만큼 반복 수행한 뒤, 마지막으로 그래프 모든 엣지에 대해 edge relaxation을 1번 수행해 준다. 이때 한번이라도 업데이트가 일어난다면 음의 사이클이 존재한다는 뜻이 되어서 결과를 구할 수 없다는 의미의 false를 반환하고 함수를 종료한다. 

 

 

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

V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 모든 정점 사이의 최단 경로를 구하는 알고리즘이다.

어떤 두 정점 사이의 최단 경로는 어떤 경유지(K)를 거치거나 거치지 않는 경로 중 하나이다. 즉, 정점 A와 정점 B 사이의 최단 경로는 A-B이거나 A-K-B이다. 만약 경유지(K)를 거친다면 최단 경로를 이루는 부분 경로 역시 최단 경로이다. 다시 말해, 만약 A-B의 최단 경로가 A-K-B라면 A-K와 K-B도 각각 최단 경로이다.

 

특징

• 순환만 없다면 음수 가중치도 가능하다.
  • 즉, 음의 간선이 포함되어 있어도 사용 가능
    음수 사이클이 있으면 정상 동작 하지 않음
• 기본적으로 동적계획법으로 접근한다. 모든 가능한 경유지에 대해서 모든 정점에서 모든 정점으로 가는 최단거리를 확인하므로 연산횟수는 V^3이고, 따라서 시간복잡도는 O(V^3)이다.
• 구현이 쉽고 모든 지점에서 최단 경로를 구하는 것이 가능하다.

 

 

---

참고)

https://jina-developer.tistory.com/118

https://www.baeldung.com/cs/dijkstra-edge-relaxation