다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘이란?

음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘 (최단 경로 문제, Shortest Path Problem)이다.

 

그래프 방향의 유무는 상관없으나, 간선(Edge)들 중에 단 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없다.

말 그대로 최단거리에 관하여 논하는 문제이기 때문이다.

 

과정

간단한 로직을 살펴보면

1. 출발 노드를 지정한다.
2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.
4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 을 갱신한다.
5. 3~4번을 반복한다.

그림으로 살펴 보겠다.

• 먼저 최단 경로를 저장하는 배열의 초기는 무한대이다.
• 1번 정점에서 시작해 모든 정점들까지의 최단 경로를 구한다고 가정한다.
• 당연하게 출발 노드는 1로 설정되고 0을 저장한다.

 

• 1번의 인접 정점들을 살피고 간선 가중치로 모두 업데이트된다.
• distance[특정 정점]과 distance[1] + (1번 정점과 특정 정점 사이의 가중치) 를 비교해 더 작은 값으로 갱신해준다.

• 다음은 아직 방문하지 않은 노드 중에 distance의 가장 작은 값을 가지는 5번 노드를 선택한다.
• 1번 노드는 방문했기 때문에 넘어간다.
• 4번 노드의 값이 distance[특정 정점] (현재 값 9) 과 distance[1] + (1번 정점과 특정 정점 사이의 가중치) ( 갱신하는 값 3) 갱신된다.

 

• 끝까지 구한다면 위에 보이는 표과 같이 1에서부터 각 노드까지의 최단경로가 구해진다.
• 1번 노드에서 5번 노드까지의 최단 경로는 distance[5]를 보면 되기 때문에 1이다

다음은 직접 자바 코드로 짜 본 다익스트라 알고리즘이다. (우선순위 큐로)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class pqDijkstraTest {
   static class Vertex implements Comparable<Vertex> {
      int no, totalDistance; // totalDistance : 출발지에서 자신까지 오는 최단거리

      public Vertex(int no, int totalDistance) {
         super();
         this.no = no;
         this.totalDistance = totalDistance;
      }

      @Override
      public int compareTo(Vertex o) {
         return this.totalDistance - o.totalDistance; // totalDistance가 작은 비용이 우선적으로 처리
      }
   }

   public static void main(String[] args) throws NumberFormatException, IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int V = Integer.parseInt(br.readLine());
      int start = 0;
      int end = V - 1;
      final int INFINITY = Integer.MAX_VALUE;

      int[][] matrix = new int[V][V];
      int[] distance = new int[V]; // 출발지에서 자신까지 오는 최단거리
      boolean[] visited = new boolean[V];

      for (int i = 0; i < V; i++) {
         StringTokenizer st = new StringTokenizer(br.readLine());
         for (int j = 0; j < V; j++) {
            matrix[i][j] = Integer.parseInt(st.nextToken());
         }
      }

      PriorityQueue<Vertex> pQueue = new PriorityQueue<Vertex>();
      
      Arrays.fill(distance, INFINITY);
      distance[start] = 0;
      pQueue.offer(new Vertex(start, distance[start]));

      Vertex current = null;
      
      while(!pQueue.isEmpty()) {

         // 1단계 : 방문하지 않은 정점들 중에 출발지에서 자신까지 오는 비용이 최단인 정점을 고려할 경유지로 선택
         current = pQueue.poll();
         if(visited[current.no]) continue;    // PQ에 남아있던 totalDistance의 최소비용보다 더 큰 상태
         
         visited[current.no] = true;
         if(current.no == end) break;
         
         // 2단계 : 선택된 current 정점을 경유지로 해서 아직 방문하지 않은 다른 정점으로의 최단거리 비용 계산하여 유리하면 update
         for(int j =0; j<V; j++) {
            // min ==> distance[current]
            if(!visited[j] && matrix[current.no][j] !=0 
                  &&distance[j] > current.totalDistance + matrix[current.no][j]) {
               distance[j] = current.totalDistance + matrix[current.no][j];
               pQueue.offer(new Vertex(j, distance[j]));
            }
         }
      }
      
      System.out.println(distance[end]);
   }
}

 

 

 

• 출처
  chanhuiseok.github.io/posts/algo-47/
• m.blog.naver.com/ndb796/221234424646
• 위키백과