[그래프 탐색] 다익스트라 알고리즘

언제 쓰이는가? 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 하나의 목적지로 가는 모든 최단 경로를 구하는 문제 모든 최단 경로를 구하는 문제 다익스트라 알고리즘 동작 원리 다익스트라 알고리즘의 기본 로직은, 첫 정점을 기준으로 연결되어있는 정점들을 추가해가면서 최단거리를 갱신하는 것이다. 정점을 잇기 전까지는 시작점을 제외한 정점들은 모두 무한대 값을 가진다. 다음과 같은 그래프가 있고, 여기서 시작점은 5번의 정점이라고 생각을 해보자. 우선순위 큐에 모든 정점들을 넣어준다. Priority Queue인덱스최단 거리50 Distance543210INFINFINFINF 큐에서 가장 위에 있는 값을 꺼내면, 인덱스는 5이고 ..

2020.06.27