다익스트라 알고리즘

다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다.

흔히 인공위성 GPS 소프트웨어 등에서 가장 많이 사용된다.

다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다.

다만 이 때 음의 간선은 포함할 수 없습니다. 물론 현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에서 사용하기 매우 적합한 알고리즘 입니다.

다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 최단 거리는 여러 개의 최단 거리로 이루어져있기 때문입니다.

작은 문제가 큰 문제의 부분 집합에 속해있다고 볼 수 있습니다.
기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있습니다.