📌 Dijkstra Algorithm

📍 What is?

그래프가 주어졌을 때, 한 정점에서 각각의 정점까지 가는 최단 겨올를 구하는 알고리즘

→ 모든 그래프가 가능한 것은 아니다.

→ 방향이 있어야 하고 간선에 가중치가 있어야 한다. (무방향일 경우에는 양방향으로 표현)

📍 Algorithm

Steps

1. 시작점 S를 기준으로 D 배열을 초기화
2. D 배열에서 가중치가 가중치가 최소인 것을 선택 → X
3. X를 기준으로 Relax 함수 수행
4. D배열에서 뽑힌 node를 S에 추가
5. S에 D배열의 모든 node가 들어있으면 종료

Code

Report 참고

📌 Hash

📍 What is?

Key를 통해 value를 저장하는 방법으로 데이터를 효율적으로 저장하고 탐색하는 방법이다.