[알고리즘 기본]다익스트라 알고리즘

다익스트라 알고리즘

한 정점으로 부터 모든 정점으로의 최단거리를 구하는 알고리즘이다. 

다만 음의 간선이 있다면 사용할 수 없다. 

 

동작 순서는 일단 출발지를 정하고, 이어져 있는 거리를 저장한다.

그 다음 부터는 가장 짧은 거리에 있는 정점을 방문하고, 해당 정점을 거쳐가는 거리가 더 짧다면 갱신, 아니면 그대로 둔다.

이런식으로 반복해서 모든 정점을 방문하면 끝나게 된다.

 

---

그래프와 인접그래프

 

 

 

 

 

다익스트라 알고리즘 시작!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

추가적으로,, 최적화에 대해 생각해본다면, 가장 짧은 거리를 탐색할 때, 우선순위 큐를 활용한다면 O(nlogN)으로 탐색이 가능하다. 

 

---

관련문제

https://www.acmicpc.net/problem/4485

4485번: 녹색 옷 입은 애가 젤다지?

https://jinniepark.tistory.com/67

[백준][4485]녹색 옷 입은 애가 젤다지?