• 다익스트라 알고리즘은 그리디와 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 ( Shortest Path ) 탐색 알고리즘이다.
• 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점을 가는 최단 경로를 알려줍니다. 단, 음의 간선을 포함하여 사용할 수 없습니다. → 벨만 포드 ( Bellman Ford ) 알고리즘
• 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 ‘ 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문’ 즉, 작은 문제가 큰 문제의 부분 집합에 속해 있다고 볼 수 있다.
  • 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있습니다.

동작 원리

구현

연습