알고리즘 - 다익스트라

자꾸 잊어서 작성..

하나의 정점에서 모든 정점까지 최소 비용 거리 구하기

ex) 가장 저렴하게 도로놓기, 최단 시간내에 목적지까지 가기 등

다익스트라 흐름

초기상태

0번 노드는 INF가 아니라 0으로 초기화 해도 됨

하나의 정점을 기준으로 설정

0번 노드를 기준

0번 노드를 기준으로 인접해서 갱신한 노드 기준으로
다시 인접 노드 가중치를 탐색

• 1번 노드를 다시 기준
  

1번 노드의 인접한 2번 노드까지 가중치를 계산해봄

1번 노드까지 오는데 가중치 2 + 여기서 2번 노드까지 가중치 1 = 3
dist[2]에 저장된 값은 6 이었으니, 갱신 필요

또한, 1번 노드의 인접한 3번 노드까지 가중치를 계산해봄

1번 노드까지 오는데 가중치 2 + 여기서 3번 노드까지 가중치 6 = 8
dist[3]에 저장된 값은 INF 이었으니, 갱신 필요

• 갱신이 발생한 2번 노드, 3번 노드를 기준으로 다시 동일하게 탐색반복

구현

int[] dist // 최단경로 거리 담고있는 배열
int[][] adj // 인접행렬 정보(단방향, 양방향에 따라 다름)
Queue q // 탐색해야하는 노드 번호 offer하는 큐

adj를 기반으로 1차원 dist 배열 초기화 // 탐색하고자 하는 노드는 0위치로 초기화, 나머지는 INF

q.offer(탐색하고자 하는 노드 번호)
while(!q.isEmpty()){
	q.poll() //큐에서 노드번호 꺼내고
    꺼낸 번호에서 인접한 노드들을 0~N-1 까지 반복문으로 탐색
    
    만약
    dist[i] = dist[i] < (dist[꺼낸 노드] + adj[꺼낸 노드][i]) ? dist[i] : (dist[꺼낸 노드] + adj[꺼낸 노드][i])
    라면, dist[i] 갱신하고, queue 다음 탐색 노드 값으로 넣어줌
    
    
}