[Algorithm] 최단 거리 알고리즘 - 다익스트라(dijkstra) 알고리즘

🔎 다익스트라(dijkstra) 알고리즘이란?

다익스트라

• 그래프의 한 정점에서 다른 모든 정점까지 최단 거리를 구하는 알고리즘이다.
• DP 문제: 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문에 작은 문제가 큰 문제의 부분 집합이다.
• 한계: 음의 간선을 포함할 수 없다. (음의 간선을 포함하는 최단 경로 탐색 알고리즘으로 ‘벨만-포드’ 가 있다.)

알고리즘 구현 방식

• 아직 방문하지 않은 정점 중 출발지에서 가장 가까운 정점 방문 → by PriorityQueue
• 해당 정점을 거쳐 갈 수 있는 정점의 거리가 이전 기록 값 보다 작으면 갱신

1. 초기 상태

A	B	C	D	E	F
INF	INF	INF	INF	INF	INF

 

 

visit 배열

A	B	C	D	E	F
false	false	false	false	false	false

 

 

 

2. A 방문 후 주변 노드 업데이트 -> 방문 처리

A	B	C	D	E	F
0	4	INF	1	INF	INF

 

visit 배열

A	B	C	D	E	F
true	false	false	false	false	false

 

 

 

 

3. 더 빠른 경로를 발견한 경우 값 업데이트

A	B	C	D	E	F
0	1	INF	1	INF	INF

 

visit 배열

A	B	C	D	E	F
true	false	false	true	false	false

 

 

• 빠른 경로를 발견하는 과정을 PriorityQueue 이용하여 구현 가능하다.
  • PQ 사용하면 가까운 노드가 먼저 꺼내지고, 이후 먼 노드는 visit 처리에 의해 값이 업데이트 되지 않음
• visit 처리는 넣을 때가 아니라 queue에서 꺼냈을 때 인근 노드의 값을 업데이트 한 후에 이뤄진다.

 

구현 코드

while (!q.isEmpty()) {

    Node curr = q.poll();
    if (visit[curr.i]) continue;

    visit[curr.i] = true;

    for (Node node: adjList[curr.i]) {
        if (visit[node.i]) continue;

        q.offer(new Node(node.i, curr.weight+node.weight));
    }

}