[알고리즘] 다익스트라(Dijkstra) 알고리즘

다익스트라(Dijkstra) 알고리즘

• 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐색 알고리즘
  • 현재까지 알고 있던 최단 경로를 계속해서 갱신해나감으로써 DP라 할 수 있음
• 시작점에서 각각의 정점으로의 최단 거리(시간, 비용)를 탐색
• '정점 중심'이므로 인접행렬, 인접리스트 사용
• 음의 간선이 존재 X
• 탐욕 기법을 사용한 알고리즘으로 MST의 Prim 알고리즘과 유사
• 인공위성, GPS 소프트웨어 등에서 가장 많이 사용

알고리즘

1. for를 통해서 s에서부터 갈 수 있는 직접 비용을 임의의 최소비용으로 초기화한다.
2. 아직 처리하지 않은 정점에서 미방문 정점들을 확인하면서 최적(최소)의 값으로 선택해서 넘어간다.