https://www.youtube.com/watch?v=XIwiZZr2l5I&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=31

📌 다익스트라

• 그래프에서 최단 거리를 구하는 알고리즘

기능	특징	시간 복잡도(노드수 : V , 에지 수 : E)
출발 노드와 모든 노드 간의 최단거리 탐색	제약조건 : 에지는 모두 양수여야함	O(ElogV)

◾ 다익스트라 알고리즘의 원리

1. 인접 리스트로 그래프 구현

• 시간복잡도 측면에서 N의 크기가 클 것을 대비해 인접 행렬 보다는 인접 리스트를 선택하여 구현하는것이 좋음
  → 인접 행렬로 표현하는 경우 발생하는 문제점
  * N 크기가 큰 경우 : 구현하지 못하는 일이 발생
  * N의 크기가 작은경우 : 에지를 찾을때 전부 찾아봐야 하기 때문에 시간이 많이 걸림

2. 최단 거리 배열 초기화

• 최단거리 배열을 만들고 출발 노드는 0, 이외의 노드는 무한으로 초기화
  → 이 때 무한은 적당히 큰 값을 사용

3. 값이 가장 작은 노드 고르기

• 최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다.

4. 최단 거리 배열 업데이트하기

• 선택된 노드에 연결된 에지 값을 바탕으로 다른 노드 값을 업데이트
• 1단계에서 저장 해 놓은 연결 리스트를 이용해 선택된 노드 에지들을 탐색하고 업데이트

5. 모든 노드가 처리 될 때 까지 3~4를 반복

• 과정 4에서 선택 노드가 될 때 마다 다시 선택되지 않도록 방문 배열을 만들어 처리