다익스트라
-
[알고리즘] 다익스트라 알고리즘 (최단거리)SW/Algorithm 2018. 1. 17. 20:00
다익스트라 알고리즘 (Dijkstra Algorithm) 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다. O(v^2)의 복잡도 이지만 우선순위큐를 사용함으로 O(Elogv)의 시간 복잡도를 가지게 된다. E는 간선 v는 노드 // E => 최악의 경우 E번의 탐색한 노드를 집어 넣는 경우가 발생한다. 시작점에서 연결되있지 않은 노드도 무한대 크기만큼 연결되어있다가정하고 알고리즘을 수행한다. E[][] 는 간선들의 크기를 나타낸다.(그래프) D[]는 시작점에서 모든 정점을 가는 최소값을 가지게 된다. q는 시작점에서 q에 있는 정점들을 방분한다. D[v]=min(D[v],D[select_v]+E[select_v][v]) 풀이 시작점 하나를 잡는다. q에 시..