다익스트라 알고리즘(Dijkstra Algorithm, 데이크스트라 알고리즘

• 다이나믹 프로그래밍을 활용한 대표적인 최단거리 알고리즘
• 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘
• 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌
• 음의 간선(간선의 비용이 음수) 사용 불가능 : 현실에서는 일어나지 않으므로 현실 세계에 적용하기 적합

a와 b 사이의 최단 경로를 찾는 데이크스트라의 알고리즘이다. 가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리를 계산하고, 작을 경우 인접 거리를 업데이트한다. 이 그림에서는 꼭짓점에 도착하면 빨간색으로 표시했다.

REF
[위키백과] 데이크스트라 알고리즘
[안경잡이개발자] 다익스트라 알고리즘 강의