📚 Reference

참고 자료 1

📜 Chapter

BFS (Breadth First Search)

‣

‣

Dijkstra algorithm

Dijkstra
다익스트라 알고리즘
그래프에서 최단 경로를 구하는 알고리즘이다.
다익스트라 알고리즘은 가중치 그래프의 한 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘이다.
음수 가중치가 없는 그래프에서만 사용할 수 있다.
Greedy(탐욕적 기법)와 Dynamic Programming(동적 계획법) 개념이 포함된다.
우선순위 큐(Heap)를 사용하면 시간 복잡도를 줄일 수 있다.

Dijkstra algorithm - 동작 과정

1. 초기화

시작 노드를 선택하고, 해당 노드까지의 최단 거리를 0으로 설정한다.
나머지 모든 노드의 거리는 ∞(무한대)로 설정한다.
우선순위 큐(Priority Queue, Min Heap)를 사용하여 방문할 노드를 관리한다.