[최단 경로] 최단 경로 알고리즘 (1) 개요

최단 경로 알고리즘

• 가장 짧은 경로를 찾는 알고리즘
• '길찾기' 문제
• 다양한 유형의 문제 존재
  • ex) 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우, 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우 등
  • 실제 코테에서는 주로 전자를 요구하는 문제가 많이 출제됨
• 그래프를 이용하여 표현함
  • 각 지점은 그래프의 노드
  • 지점 간 연결된 도로는 그래프의 간선
• 주요 최단 경로 알고리즘
  • 다익스트라 최단 경로 알고리즘
  • 플로이드 워셜
  • 벨만 포드 알고리즘
  • 1, 2가 코테에서 주로 출제
• 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 적용됨