[Java] 다익스트라(Dijkstra Algorithm)

서정범·2023년 3월 13일
algorithmsearch
0

자료구조와 알고리즘

목록 보기
8/30

다익스트라 알고리즘

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

음의 가중치가 없는 그래프에서 여러 개의 노드가 있을 때, 특정한 한 정점(=노드)에서 출발하여 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘입니다. 현실 세계에서의 길(간선)은 음의 간선을 가지지 않으므로 해당 알고리즘은 실제로 인공위성 GPS 소프트웨어 등에서 가장 많이 사용됩니다.

다익스트라 알고리즘은 두 가지 특성을 가집니다.

  1. 방문하지 않은 노드중에서 가장 비용이 적은 노드를 선택한다 ⇒ 그리디 알고리즘
  1. 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다 ⇒ 다이나믹 프로그래밍

두가지의 특성을 간단하게 정리하자면 다음과 같습니다.

그리디 알고리즘

말 그대로 탐욕 알고리즘을 의미하고 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법을 의미합니다.

최적해를 구하는데 사용하는 근사적인 방법으로 해당 방식에 있어서 가장 중요한 것은 여러 경우 중 하나를 결정해야 할 때 마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 것입니다.

하지만, 순간마다 하는 선택은 그 순간에 대해서는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없습니다.

해당 페이지에서 정말 잘 정리해주셔서 링크를 가져왔습니다.

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬

동적 계획법

동적 계획법은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있습니다.

해당 방식을 알아보기 전에 피보나치 수열을 한번 들여다 봅시다.

피보나치 수열은 아래와 같은 점화식으로 정의되는 수열입니다.

Fn=Fn−1−Fn−2F_n = F_{n-1} - F_{n-2}

이와같은 특징으로 피보나치 수열의 경우 재귀 함수를 사용하여 구현합니다. 

int fibo(int n) {
	if (n <= 2)
		return 1;
	else
		return fibo(n-1) + fibo(n-2);
}

이와 같은 방식을 구현됩니다.

해당 방식은 연산이 중복되는 것을 볼 수 있습니다.

이로 인해서 동적 계획법에서는 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용 합니다.

DP는 2가지 조건을 만족할 때 사용하는데,

  1. Overlapping Sub-problems(겹치는 부분 문제)
  1. Optimal Substructure(최적 부분 구조)

이 이상은 이야기가 길어질 것 같으므로 이번에도 역시 링크를 빌려 오겠습니다.

동작 과정

  1. 출발 노드를 설정
  2. 최단 거리 테이블 초기화
  3. 방문 하지 않는 노드 중에서 최단 거리(가중치)가 가장 짧은 노드 선택
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
  5. 위 과정에서 3, 4번 반복

특징

  1. 그리디 알고리즘 + 다이나믹 프로그래밍 기법
  1. 가중치가 양수일 때만 사용 가능

코드

Basic Code(Using List)

import java.util.ArrayList;
import java.util.Scanner;

/*
sample input
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
 */

// 도착 지점과, 도착지점으로 가는 비용을 의미하는 클래스를 정의한다.
class Node {
  int idx;
  int cost;

  // 생성자
  Node(int idx, int cost) {
    this.idx = idx;
    this.cost = cost;
  }
}

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    // 노드와 간선의 개수
    int V = scanner.nextInt();
    int E = scanner.nextInt();

    //출발 지점
    int start = scanner.nextInt();

    // 1. 인접리스트를 이용한 그래프 초기화
    ArrayList<ArrayList<Node>> graph = new ArrayList<>();

    for(int i = 0; i < V + 1; i++) {
      // 노드의 번호가 1부터 시작하므로, 0번 인덱스 부분을 임의로 만들어 놓기만 한다.
      graph.add(new ArrayList<>());
    }

    // 그래프에 값을 넣는다.
    for(int i = 0; i < E; i++) {
      // a로 부터 b로 가는 값은 cost이다.
      int a = scanner.nextInt();
      int b = scanner.nextInt();
      int cost = scanner.nextInt();

      // 무방향 그래프인 경우 해당과 같이 해줄 필요가 있다.
      graph.get(a).add(new Node(b, cost));
      graph.get(b).add(new Node(a, cost));
    }

    // 2. 방문 여부를 확인할 boolean 배열, start 노드로부터 end 노드 까지의 최소 거리를 저장할 배열을 만든다.
    boolean[] visitied = new boolean[V + 1];
    int[] dist = new int[V + 1];

    // 3. 최소 거리 정보를 담을 배열을 초기화 한다.
    for(int i = 0; i < V + 1; i++) {
      // 출발 지점 외 나머지 지점까지의 최소 비용은 최대로 지정해둔다.
      dist[i] = Integer.MAX_VALUE;
    }
    // 출발 지점의 비용은 0으로 시작한다.
    dist[start] = 0;

    // 4. 다익스트라 알고리즘을 진행한다.
    // 모든 노드를 방문하면 종료하기 때문에, 노드의 개수 만큼만 반복을 한다.
    for(int i = 0; i < V; i++) {
      // 4 - 1. 현재 거리 비용 중 최소인 지점을 선택한다.
      // 해당 노드가 가지고 있는 현재 비용.
      int nodeValue = Integer.MAX_VALUE;
      // 해당 노드의 인덱스(번호).
      int nodeIdx = 0;

      // 인덱스 0은 생각하지 않기 때문에 0부터 반복을 진행한다.
      for(int j = 1; j < V + 1; j++) {
        // 해당 노드를 방문하지 않았고, 현재 모든 거리비용 중 최솟값을 찾는다.
        if(!visitied[j] && dist[j] < nodeValue) {
          nodeValue = dist[j];
          nodeIdx = j;
        }
      }

      // 최종 선택된 노드를 방문처리 한다.
      visitied[nodeIdx] = true;

      // 4 - 2. 해당 지점을 기준으로 인접 노드의 최소 거리 값을 갱신한다.
      for(int j = 0; j < graph.get(nodeIdx).size(); j++) {
        // 인접 노드를 선택한다.
        Node adjNode = graph.get(nodeIdx).get(j);

        // 인접 노드가 현재 가지는 최소 비용과
        // 현재 선택된 노드의 값 + 현재 노드에서 인접 노드로 가는 값을 비교하여 더 작은 값으로 갱신한다.
        if(dist[adjNode.idx] > dist[nodeIdx] + adjNode.cost) {
          dist[adjNode.idx] = dist[nodeIdx] + adjNode.cost;
        }
      }
    }

    // 5. 최종 비용을 출력한다.
    for(int i = 1; i < V + 1; i++) {
      if(dist[i] == Integer.MAX_VALUE) {
        System.out.println("INF");
      } else {
        System.out.println(dist[i]);
      }
    }
    scanner.close();
  }
}

Using Priority Queue

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

/*
sample input
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
 */

public class Main {
  static int V, E, start;
  static ArrayList<ArrayList<Node>> graph;

  static class Node {
    int idx, cost;

    Node(int idx, int cost) {
      this.idx = idx;
      this.cost = cost;
    }
  }

  public static void main(String[] args) throws IOException {

    // 초기화
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    // Node의 개수와 간선의 개수 입력받기
    V = Integer.parseInt(st.nextToken());
    E = Integer.parseInt(st.nextToken());

    // 시작 지점 입력 받기
    start = Integer.parseInt(br.readLine());

    graph = new ArrayList<ArrayList<Node>>();
    // Graph 초기화
    for(int i = 0; i < V + 1; i++) {
      graph.add(new ArrayList<>());
    }

    // graph table 구축
    for(int i = 0 ; i < E; i++) {
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      int cost = Integer.parseInt(st.nextToken());

      //무향 그래프라고 가정
      graph.get(a).add(new Node(b, cost));
      graph.get(b).add(new Node(a, cost));
    }

    // Priority Queue를 사용하면 visited[]를 사용하지 않는다.
    //distance table 초기화
    int[] dist = new int[V + 1];

    // distance table 초기화
    for(int i = 0 ; i < V + 1; i++) {
      dist[i] = Integer.MAX_VALUE;
    }

    // 주의점 1. 다익스트라 알고리즘의 최소비용을 기준으로 추출해야 한다. 최대 비용을 기준으로 하는 경우 최악의 경우 지수시간 만큼의 연산을 해야한다.
    PriorityQueue<Node> q = new PriorityQueue<>(((o1, o2) -> Integer.compare(o1.cost, o2.cost)));

    // 처음에는 시작 노드로 가는 값이 가장 짧은 비용을 갖는 노드이다.
    // 즉, 도착 정점은 start, 비용은 0인 노드를 가장 먼저 선택할 것이다.
    q.offer(new Node(start, 0));
    // 해당 노드를 선택한 것이나 마찬가지 이므로, dist[start] = 0으로 갱신.
    dist[start] = 0;
    while (!q.isEmpty()) {
      Node curNode = q.poll();

      // 목표 정점이 꺼내 졌다면, 해당 노드까지는 최솟값 갱신이 완료 되었다는 것이 확정이다.(다익스트라 알고리즘)
      // 따라서, 반복문을 종료해도 되지만, 해당코드는 시작 정점에 대하여 모든 정점으로의 최단 경로를 구하는 것을 가정한다.
      // 아래 주석된 코드는 목표 정점이 구해졌다면 빠르게 탈출할 수 있는 조건이다.
      /*
      if(curNode.idx == end) {
        System.out.println(dis[curNode.idx]);
        return;
      }
       */

      // 꺼낸 노드 = 현재 최소 비용을 갖는 노드.
      // 즉, 해당 노드의 비용이 현재 dist배열에 기록된 내용보다 크다면 고려할 필요가 없으므로 스킵한다.
      // 주의점2. 중복노드 방지1 : 만일, 이코드를 생략한다면, 언급한 내용대로 이미 방문한 정점을 '중복하여 방문'하게 된다.
      // 만일 그렇다면, 큐에 있는 모든 다음 노드에 대하여 인접 노드에 대한 탐색을 다시 진행하게 된다.
      // 그래프 입력이 만일 완전 그래프의 형태로 주어진다면, 이 조건을 생략한 것 만으로 시간 복잡도가 E^2에 수렴할 가능성이 생긴다.
      if(dist[curNode.idx] < curNode.cost) {
        continue;
      }
      // 좀만 더 추가적으로 설명을 하자면, 해당 코드 밑에서 실행하는 코드는
      // 가장 최소 거리값을 가지고 있는 node를 선택했고, 그 이웃 노드의 거리값이 수정이 되는 경우에 queue에 넣어둔다.
      // 만약 수정된 노드를 바로 꺼낸다면 dist[curNode.idx]와 curNode.cost는 같은 값을 가질 것이다.
      // 그렇다면, 다른 경우는 다른 최소 거리값을 가진 Node를 꺼내고 또 한번 거리 값을 수정 했을 경우 이전에 넣은 queue가 위의 조건을 만족해 버린다.
      // 즉, dist[curNode.idx]가 curNode.cost보다 작아지는 것이다.


      // 선택된 노드의 모든 주변 노드를 고려한다.
      for(int i = 0; i < graph.get(curNode.idx).size(); i++) {
        Node nxtNode = graph.get(curNode.idx).get(i);

        // 주변 노드까지의 현재 dist값(비용)과 현재 선택된 노드로부터 주변 노드로 가는 비용을 비교하고, 더 작은 값을 선택한다.
        // 주의점 3. 중복노드 방지2 : 만일, 조건문 없이 조건문의 내용을 수행한다면 역시 중복노드가 발생한다.
        // 간선에 연결된 노드를 모두 넣어준다면 앞서 언급한 정점의 시간 복잡도 VlogV를 보장할 수 없다.
        // 마찬가지로 E^2에 수렴할 가능성이 생긴다. 따라서 이 조건 안에서 로직을 진행해야만 한다.
        if(dist[nxtNode.idx] > curNode.cost + nxtNode.cost) {
          dist[nxtNode.idx] = curNode.cost + nxtNode.cost;
          // 위의 코드에서 curNode.cost 대신 dist[curNode.idx]가 들어가도 문제 없다.
          // 갱신된 경우에만 큐에 넣는다.
          q.offer(new Node(nxtNode.idx, dist[nxtNode.idx]));
        }
      }
    }

    // 결과 출력
    System.out.println(Arrays.toString(dist));
  }
}

시간 복잡도

다익스트라 알고리즘은 두 가지 방식으로 구현 가능합니다.

1. 순차 탐색
2. 우선순위 큐

순차 탐색

노드를 V(Vertex)라고 할 때, 최소 비용을 갖는 노드를 선택하는 과정은 일반적인 구현에서는 최악의 경우 모든 노드를 확인해야 하고, 이것이 V번 반복하기 때문에 O(V2)O(V^2)의 시간 복잡도를 갖습니다.

T(n)=O(V2)T(n) = O(V^2)

우선순위 큐

우선 순위 큐는 리스트에서 방문하지 않은 노드에 한해서 고려할 필요가 없다는 특징을 활용합니다. 즉, 갱신하는 주변 노드 값에 대해서만 다음 최소 비용을 갖는 노드를 선택해주면 된다는 것이 핵심입니다. 우선순위 큐에 들어가는 노드의 수 = 갱신해야 하는 주변 노드의 수이다. 즉, 갱신해야 하는 주변 노드의 수 = 갱신해야 하는 주변 노드로의 간선의 수를 의미합니다. 우선 순위 큐에 삽입하는 최대 횟수는 간선의 개수이다. 모든 간선에 대하여 삽입 연산이 발생하기 때문에 최대 O(ElogE)O(ElogE)의 시간이 걸릴 것입니다. 여기서, 희소 그래프의 경우 E≤V2E ≤ V^2이므로, 최대 O(ElogV)O(ElogV)의 시간이 걸린다고 볼 수 있습니다. 각 노드들을 우선 순위 큐에 추출해주는 연산에 대해서는 최대 V개의 노드에 대하여 우선 순위 큐에서 추출할 것이므로 최대 O(VlogV)O(VlogV)의 시간이 걸릴 것이고 따라서 최대 모든 노드, 간선에 대하여 우선 순위 큐를 계산해 줘야 하므로 O((V+E)logE)O((V+E)logE)의 시간이 걸릴 것입니다.

T(n)=O((V+E)logE)T(n) = O((V+E)logE)

다익스트라 알고리즘은 선택이 된 노드의 경우 더이상 최소 비용이 이루어지지 않는다는 특징을 가지고 있습니다. 즉, 최소 비용의 갱신을 갖는 노드로 선택이 되었다면, 그 노드는 앞으로 더이상 다른 노드의 방문과는 관계 없이 항상 값이 갱신되지 않을 것이라는 것입니다.

장단점

장점

  1. 벨만-포드 알고리즘에 비해 좀 더 효율적이기 때문에 그래프가 큰 경우에도 사용할 수 있습니다.

단점

  1. 음수인 가중치를 가진 간선이 있는 경우에는 사용할 수 없습니다.

Reference

profile
서정범
개발정리블로그
이전 포스트

[Java] DFS & BFS

다음 포스트

[Java] 벨만 포드(Bellman-Ford Algorithm)

0개의 댓글