최단 경로 알고리즘

1. 개요

그리디 알고리즘 해결 방식의 일종

그리디 알고리즘이란?

• 최적화 문제를 해결하는 알고리즘

  • 최적화 문제: 가능한 해들 중 가장 좋은 해를 찾는 문제

• 데이터 간의 관계를 고려하지 않고 수행 과정에서 최솟값/최댓값을 가진 데이터를 선택하는 알고리즘 (근시안적 선택)

  • 근시안적 선택으로 찾은 부분 최적해를 모아 문제 해결

  • 욕심쟁이/탐욕 알고리즘 등으로 불림

• 일단 한 번 선택하면, 다시 번복하지 않음 (선택한 데이터를 다시 버리지 않음)

• 대부분의 그리디 알고리즘들은 매우 단순하며, 제한적인 문제들을 해결함

최단 경로 알고리즘이란? 주어진 가중치 그래프에서의 최단 경로를 찾는 알고리즘

• 종류

  • 단일 정점으로부터 시작하는 최단 거리 알고리즘

    • 다익스트라 알고리즘

    • 벨만-포드 알고리즘 (음수 가중치)

  • 모든 정점 간의 최단 거리 알고리즘

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

1.1. 다익스트라 알고리즘이란

• 음의 가중치가 없는 그래프에서 사용하는 최단 경로 알고리즘

• 시작 정점인 s에서 모든 정점까지의 최단 거리 계산

• 출발점으로부터 최단 거리가 확정되지 않은 정점들을 우선 고려

  • 출발점으로부터 가장 가까운 정점 추가

  • 해당 정점의 최단 거리 확정

• 최단 거리 계산

  

  • D[w]: 출발점 s부터 w까지의 최단 거리
  • D[V_min] + 간선(V_min, W)의 가중치가 D[w]보다 작을 경우
    • D[w] = D[V_min] + 간선(V_min, w)의 가중치

2. 알고리즘

• Input: 가중치 그래프 G=(V, E) , |V|=n , |E|=m

• Output: 출발점 s로부터 (n-1)개의 각 정점까지의 최단 거리를 저장한 배열 D

D[ : ] = INF; D[s] = 0; // D[v]에는 출발점 s로부터 정점 v까지의 거리를 저장
while(정점 s로부터의 최단 거리가 확정되지 않은 정점이 있으면)
    (1) 최단 거리가 확정되지 않은 정점 V에 대해 D[v]가 최소인 정점 V_min을 선택, D[V_min] 확정
    (2) s에서 V_min을 통해 우회 가능한 정점 w에 대해 V_min으로 우회하는 경로의 거리가 D[w]보다 짧은 경우 D[w] 갱신    // 최단 거리 갱신
return D

• (2)의 간선 가중치 갱신 방법

  

  • V는 모든 정점의 집합, T는 최단 거리가 확정된 정점의 집합
  • T에 속한 정점 중, 정점 s로부터의 거리가 V_min을 경유하는 경우
    • 현재 거리보다 더욱 단축되는 w가 있으면 D[w] 갱신

시간 복잡도

• while 반복문이 (n-1)회 반복되고, 1회 반복될 때
  • (1)에서 최소의 D[V]를 가진 점 V_min 탐색 => $O(n)$
  • (2)에서 D[w]를 갱신하는 데 소요되는 시간 => $O(n)$
• $(n-1) \times { O(n) + O(n) } = O(n^{2})$
  • Prim 알고리즘 등 binary heap을 사용하면 $O(m\log n)$ (m:간선 개수)
  • 간선 개수가 O(n)일 경우, 시간 복잡도 $O(n\log n)$