📌 Dijkstra Algorithm
📍 What is?
그래프가 주어졌을 때, 한 정점에서 각각의 정점까지 가는 최단 겨올를 구하는 알고리즘
→ 모든 그래프가 가능한 것은 아니다.
→ 방향이 있어야 하고 간선에 가중치가 있어야 한다. (무방향일 경우에는 양방향으로 표현)
📍 Algorithm
Steps
- 시작점 S를 기준으로 D 배열을 초기화
- D 배열에서 가중치가 가중치가 최소인 것을 선택 → X
- X를 기준으로 Relax 함수 수행
- D배열에서 뽑힌 node를 S에 추가
- S에 D배열의 모든 node가 들어있으면 종료
Code
Report 참고
📌 Hash
📍 What is?
Key를 통해 value를 저장하는 방법으로 데이터를 효율적으로 저장하고 탐색하는 방법이다.