[알고리즘] 최단 경로 문제(Shortest-path Problem)

그래프 이론에서 최단 경로 문제는 경유하는 간선들의 가중치 합이 최소가 되도록 하는 두 정점 사이의 경로를 찾아내는 문제를 의미한다.

최단 경로 유형

• 단일 출발(single source)
  정점 V에서 출발 --- 모든 정점에 도착
  
  
• 단일 도착(single destination)
  모든 정점에서 출발 --- 정점 V에 도착
  단일 도착 문제에서 그래프 내 정점들을 모두 거꾸로 뒤집으면 단일 출발 문제로 풀 수 있다.
  
  
• 단일 쌍(single pair)
  정점 V1에서 출발 --- 정점 V2에 도착
  (일반적으로 최단 경로는 단일 쌍 최단 경로를 의미한다.)
  
  
• 전체 쌍(all pairs)
  모든 정점에서 출발 --- 모든 정점에 도착

최단 경로 문제를 해결하기 위한 알고리즘으로는 다익스트라 알고리즘(Dijkstra's algorithm), 벨만-포드 알고리즘(Bellman-Ford algorithm), 플로이드-워셜 알고리즘(Floyd-Warshall algorithm) 등이 있다.