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

• 특정한 정점에서 다른 모든 정점으로 가는 최단 거리를 구할 때 사용하는 알고리즘 중의 하나
  최단 거리는 여러개의 최단 거리로 이루어져 있다. (다이내믹 프로그래밍)

특징:
1) 간선의 가중치(weight)가 음수이면 적용 불가능 함
2) 시작점의 위치가 정해져 있을 경우에 적용한다.

방법론:
기본적인 컨셉은 방문하지 않은 노드를 방문하면서 최단거리를 갱신하는데 있다.
따라서 아래와 같은 배열이 기본적으로 필요하다.

dist[i] = 시작 → i의 최단거리
check[i] = i를 검사했으면 true, 아니면 False

1) 출발 노드 설정 dist = [INF] * (V+1), dist[start] = 0
2) 출발 노드를 기준으로 각 노드의 최단거리 비용을 갱신
3) 방문하지 않은 노드 선택 (현재 출발 노드를 기준으로 갱신한 노드 중에 가장 비용이 적은 노드를 선택)
4) 출발 노드 + 특정노드로 가는 비용을 고려해서 최소 비용 갱신
5) 3)~4) 과정을 반복

시간 복잡도:
인접 행렬: O(V2)
인접 리스트: O(V2)
힙 사용: O(ElogE) -> O(ElogV)로 줄이려면 BST를 사용하면 됨

참고 URL: https://m.blog.naver.com/ndb796/221234424646

<update 필요>
인접 리스트, 인접 행렬에 대해서.