다익스트라(Dijkstra)

🐢 다익스트라의 사용

Q. 다익스트라는 언제 사용하는 알고리즘일까?

A. 시작점이 주어졌을때, 최소 비용으로 (혹은 최대 이익)으로 정점들을 거쳐서 다른 모든 정점까지 가는 비용을 알 수 있다.

 

🐢 기본 구조

// pair는 다음 노드로 가기위한 비용과 다음 노드의 정보가 들어있다
ArrayList<pair>[] adj = new ArrayList[N]; 

// dp는 현재 노드에서 특정 노드까지의 비용을 업데이트하기 위한 배열
int dp[N];

// 시작점을 제외한 모든 노드들에 대해 비용을 최대로 잡아준다, 시작점은 0
for (int i = 0; i < N; i++) 
    dp[i] = INF; 
dp[S] = 0;

adj 리스트 배열에 모든 간선들에 대해서 시작점을 기준으로 넣어준다

dp[i] == S부터 i까지의 최소 비용

dp배열의 업데이트 방법?

1. S에서부터 시작하는 가장 짧은(비용이 낮은) 길을 찾는다
2. 그 짧은 길을 거쳐서 다른 정점으로 가는 모든 경우의 수를 생각해본다
3. 그 해당 정점까지의 비용이 기존 dp에 저장되어있는 값보다 작다면 없데이트해준다
4. 모든 간선을 확인할 때까지 반복한다

가장 비용이 작은(거리가 짧은) 간선을 찾기 위해서 PriorityQueue를 사용하자!

PriorityQueue<Object> pq = new PriorityQueue<>(Comparator.comparingInt(s -> s.비용);

pq.push(new Object(0, S));
while (!pq.isEmpty())
{
    Object obj = pq.poll();
    
    if (dp[obj.다음정점] < obj.비용) continue;

    for (Object next_obj : adj[obj.다음정점])
    {
        if (dp[obj.다음정점] + next_obj.비용 < dp[next_obj.다음정점])
        {
            dp[next_obj.다음정점] = dp[obj.다음정점] + next_obj.비용;
            pq.add(new Object(dp[next_obj.다음정점], next_obj.다음정점);
        }
    }
}

System.out.println(dp[END]);

 

🐢 관련문제

1916번 최소 비용 구하기 2665번 미로만들기 4485번 초록색 옷 입은 애가 젤다지? 1238번 파티 1162번 도로포장