[Algorithm] Dijkstra (다익스트라 알고리즘) 이론 설명
다익스트라 알고리즘 Overview 그래프 최단 경로를 찾는 알고리즘으로서, 특정한 하나의 정점 노드에서 다른 모든 정점 노드로 가는 최단 경로를 구하는 알고리즘입니다. ( 시간복잡도: $O(V^{2}$) ) 다익스트라 알고리즘은 그리디와 동적 프로그래밍 알고리즘 모두로 보고 있습니다. 왜 둘다로 여기는지는 참고 사이트 와 아래 Introduce를 확인해주세요. * 다익스트라 알고리즘은 음의 간선이 존재하지 않는 경우 사용할 수 있습니다. Introduce 카카오나 네이버 맵 등에서 출발지부터 도착지까지 가장 빠른 경로를 어떻게 찾아서 알려줄까요? 이럴 때 다익스트라 알고리즘을 사용합니다. 다익스트라 알고리즘은 컴퓨터 과학자인 Edsger W.Dijkstra로부터 1956년에 만들어진 그래프에서 단일 최단 경로를 찾는 알고리즘입니다. 이는 특정 정점으로부터 연결된 모든 정점의 최단 경로를 찾는 알고리즘이란 뜻입니다. 이 과정에서 도착 정점 뿐만 아니라 다른 모든 정점의 최단 경로까지 찾습니다. 즉, 매번 최단 경로의 정점을 선택해 탐색 반복하며(그리디 알고리즘 성격), 정점과 정점 사이 경로 갱신을 위해 이전에 구했던 경로 값을 사용합니다. (다이나믹 알고리즘 성격) 다익스트라 알고리즘은 유방향(directed)과 무방향(undirected)에서 양의 간선인 경우 동작 가능합니다. 유방향 (directed): 방향이 있는 간선을 가지는 그래프 (간선은 단방향 관계를 나타냄) 무방향 (undirected): 방향이 없는 간선을 가지는 그래프 (간선은 양방향 관계를 나타냄) Algorithm 1. 출발 정점 설정 (출발 정점 최소 비용은 0으로 설정, 자기자신으로 이동하는 비용이기 때문) 2. 정점 방문 여부를 체크하는 리스트 생성 (visited list) 3. 최단 거리 리스트 생성 (dijkstra list) 4. 선택된 정점의 인접한 정점들 중, 아직 방문하지 않았고 비용이 가장 적은 정점 선택 5. 4번