Dijkstra

다익스트라(dijkstra)

📔 다익스트라(dijkstra) 란 다익스트라를 들어가기 전에... 최단 경로란 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로 간선의 가중치가 균일(1)할 경우 BFS를 사용 음의 가중치를 허용하지 않음 하나의 시작 정점에서 끝 정점까지의 최단경로 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다. 시작 정점(s) 에서 끝 정점(t) 까지의 최단 경로에 정점 x 가 존재한다. 이때, 최단 경로는 s 에서 x 까지의 최단경로와 x 에서 t 까지의 최단경로로 구성된다. 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다. 아래 코드의 경우 시간복잡도는 O(N^2) 이다. 만약 우선순위큐를 이용하게 된다면 O(NlogN..