다익스트라

다익스트라 최단경로 알고리즘

1) 최단 경로 탐색 알고리즘으로 특정한 하나의 정점에서 다른 모든 정점(One-To_ALL)으로 가는 최단경로를 파악(단, 음의 간선 제외-> 벨만포드알고리즘 사용할 것)
2) Dijkstra = DP : 최단거리는 여러개의 최단거리로 이루어지기 때문

다익스트라 구현 과정_Priority Queue

1. 한정점으로부터 다른정점까지의 최단거리를 저장하는 dist[] 배열 <-사용하는것이 중요.
   초기화로 INF를 지정한다. -> 최단거리는 최솟값을 찾는 것이므로 해당 범위내의 값보다 큰 값을 저장해야한다.
2. 시작지점은 0으로 시작한다.dist[start]=0;
3. 큐에 {정점, 비용}을 넣는다.->첫시작은 비용 =0
4. 해당정점을 꺼내서 인접리스트를 탐색한다.(O(E))
5. (중요) 인접리스트를 돌면서 dist[인접리스트]와 dist[해당정점]+인접리스트_비용 을 비교해서 최소값을 넣어주고 큐에 {정점,최소비용}을 넣어준다.

if(dist[start]+w<dist[adj])
{
	dist[adj] = dist[start]+w;
	pq.add(new Node{adj,dist[adj]);
}

6. 3번부터 5번까지 반복을 하고 만약에 dist[정점]이 비용보다 작으면 더 생각할 필요가 없어 인접리스트 탐색을 할 필요가 없다.
   예를들어 1->5 비용 :15, 1->2->5 비용 :10일 경우 dist[5]=10이 되어있음 근데 5로가는 비용 15가 큐에서나오면 비교할 필요가 없기때문에 진행 X

if(dist[p.startPos]<p.price)
{
	continue;
}

시간복잡도

O(ElogV)(E : 간선의 개수)
1. 한정점에서 주변 간선을 확인하는 작업
O(E)
2. 우선순위큐에서 확인하는 작업
O(ElogE)
3. V^2 > E이므로 O(logE) = (logV)