오늘은 최단경로 문제에 빈출되는 알고리즘들에 대해 이론 설명을 해보겠습니다.

알고리즘 공부를 처음 하시는 분들은 최단경로 문제를 풀이할 때, 다익스트라, 벨만 포드, 플로이드 워샬 등의

알고리즘 기법이 헷갈리거나 익숙치 않을 수 있습니다. 기초를 단단히 다지고 넘어가는 게 좋을 것 같아요:)

 

우선, 최단 경로 탐색 알고리즘에는 종류가 많습니다. 각각의 특징과 목적에 따라 사용됩니다.

(여기선 Dijkstra, Bellman-Ford, Floyd-Warchall만 알아봅시다)


단일 출발지 최단 경로 알고리즘

  • 특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 계산하는 알고리즘
    ex) 다익스트라, 벨만-포드, A 알고리즘, SPFA(Shortest Path Faster Algorithm)

모든 쌍 최단 경로 알고리즘

  • 그래프의 모든 노드 쌍 간의 최단 경로를 계산하는 알고리즘
    ex) 플로이드-워샬, 존슨 알고리즘

특정 목표를 위한 최단 경로 알고리즘

  • 특정 조건에서 최적의 경로를 탐색하는 알고리즘.
    ex) 프림 알고리즘, 크루스칼

실시간 탐색 

  • ex) 다이나믹 라우팅 알고리즘 (Dynamic Routing Algorithms)
    -> computer network 공부하셨다면 OSPF나 BGP에서 쓰이는 걸로 많이 알려져있죠

1. Dijkstra Algorithm

 

목적 :

  • 단일 출발지 최단 경로를 찾는 데 사용된다.
  • 그래프의 특정 출발 노드에서 다른 노드까지의 최단 경로를 계산한다.

특징 :

  • 음수 가중치 허용 x : 간선 가중치가 음수일 경우 결과가 올바르지 않게 된다.
  • 우선 순위 큐(힙) 사용 : 최소 비용 정점을 효율적으로 찾기 위해 Priority Queue 자료구조를 사용합니다.
  • 그리디 알고리즘 : 현재 최단 경로를 기반으로 점진적으로 최적 해를 찾아간다.

시간 복잡도 :

  • 인접 리스트 + 우선 순위 큐(힙 사용)  : O((V+E)logV)
  • 인접 행렬 : O(V^2)

동작 방식 :

  • 시작 노드의 비용을 0으로 설정하고, 나머지 노드는 무한대로 설정한다.
    -> 이 말의 뜻은, 시작 노드에서 어디로도 이동하지 않았기 때문에 초기 비용은 0으로 설정하고, 아직 도달하지 않은 노드에 대해서는 INF 값을 지정한 후, "최소 비용"이 발견되는 노드로 이동합니다.
  • 우선 순위 큐에서 가장 작은 비용을 가진 노드를 꺼내고, 해당 노드의 이웃 노드를 탐색한다.
  • 탐색한 이웃 노드의 거리가 더 짧아지면 (지금 계산한 비용보다 더 적은 비용이 드는 노드) 갱신한다.
  • 모든 노드를 탐색할 때까지 반복

 

2. Bellman-Ford Algorithm

 

목적 :

  • 단일 출발지 최단 경로를 찾는 데 사용된다.
  • 간선 가중치가 음수인 경우에도 동작한다.
  • 음수 사이클(총합이 음수인 사이클)도 탐지할 수 있다.

특징 :

  • 음수 가중치 허용 : 음수 가중치가 있어도 정확히 동작
  • 동적 프로그래밍 기반 : 모든 간선을 반복적으로 확인하며 최단 경로를 갱신한다.
  • 음수 사이클이 존재하면 최단 경로를 계산하지 않고 에러로 처리할 수 있다.

 

시간 복잡도 : O(VE)

 

동작 방식 :

  • 출발 노드의 거리를 0으로 설정하고, 나머지 노드는 무한대로 설정한다.
  • 모든 간선을 V-1번 반복하면서, 각 간선의 시작과 끝 노드를 확인하며 최단 경로를 갱신한다.
  • V-1번 반복 후, 한번 더 확인하여 음수 사이클이 있는지 확인한다.

3. Floyd-Warchall Algorithm

 

목적 :

  • 모든 노드 쌍 간의 최단 경로를 찾는 데 사용한다.

 

특징 :

  • 음수 가중치 허용 : 음수 가중치 간선을 허용하지만, 음수 사이클이 있으면 결과가 올바르지 않을 수 있다.
  • 동적 프로그래밍 기반 : 경유지를 하나씩 추가하며 최단 경로를 갱신한다.
  • 인접 행렬 사용 : 거리 정보를 행렬 (ex. dist[i][j])로 표현하며, 갱신된 최단 거리를 저장한다.

 

시간 복잡도 : O(V^3)

 

동작 방식 :

  • 초기화 : 인접 행렬에 직접 연결된 거리를 저장하고, 연결되지 않은 경우 무한대로 설정한다.
  • 경유지 노드 k를 반복적으로 추가하며, 노드 i에서 j까지 가는 최단 경로를 d[i][j] = min(d[i][j], d[i][k] + d[k][j])로 갱신한다.
  • 모든 노드에 대해 반복한다.

 

'알고리즘(JAVA)' 카테고리의 다른 글

BFS(너비 우선 탐색) 알고리즘 - JAVA/자바  (2) 2024.10.24

티스토리툴바