[Algorithm] 최단경로 알고리즘

가중치를 가진 유향 그래프에서 목적지에 이르는 모든 가능한 경로 중 최단 경로를 찾는 알고리즘이다.

다익스트라, 벨만-포드, 모든쌍 최단경로, 싸이클이 없는 그래프의 최단 경로가 있다.

 

최단경로 문제에서 입력 그래프는 크게 두가지 유형을 갖는다.

1) 모든 간선 가중치가 음이 아닌 일반적인 경우 -> 다익스트라 알고리즘

2) 음의 가중치가 존재하는 경우 -> 벨만-포드 알고리즘

주의할 것은 음의 가중치는 허용하나 가중치의 합이 음인 싸이클은 절대 허용하지 않는다.

 

다익스트라 알고리즘

최소신장트리를 위한 프림 알고리즘과 원리가 거의 같다.

프림 알고리즘에서는 간선을 연결하는데 필요한 최소 비용을 저장하지만,

다익스트라에서는 시작 노드에서의 최소비용이 저장된다.

 

다익스트라 알고리즘 초기상태

먼저, 시작노드의 값을 0으로 초기화하고 나머지 값을 아주 큰 수로 초기화한다.

S에는 경로에 포함된 노드들이 저장되고, d에는 노드까지 최소비용이 저장된다.

시작노드를 S에 저장

시작노드를 S에 저장하고, 연결된 노드에 최소비용을 계산한다.

최소비용 결정된 노드 추가

최소비용으로 결정된 노드를 S에 저장한다. 그리고 연결된 노드의 최소 비용을 계산한다.

최소 비용 S에 추가 후 최소비용 변경

그 다음, 노드 중 최소비용인 노드를 다시 S에 저장하고 연결된 노드의 최소비용을 계산한다. 18이었던 값은 더 작은 값인 10으로 변경되었고, 11은 12보다 작기 때문에 유지되었다. 이와 같이 경로와 경로에 따른 비용을 계산하면서 반복하면 시작노드에서 각각 노드에 도달하기까지 최단거리를 그리게 된다.

다익스트라 최단경로 알고리즘 결과

일반적인 다익스트라 알고리즘 자바 구현

import java.util.*;

class Node {
  private int index;
  private int distance;
  
  public Node(int index, int distance) {
    this.index = index;
    this.distance = distance;
  }

  public int getIndex() {
    return this.index;
  }

  public int getDistance() {
    return this.distance;
  }
} // end Node Class

class Main {

  public static final INF = (int) 1e9;
  public static int n, m, start;
  public static List<List<Node>> graph = new ArrayList<>();
  public static boolean[] visited = new boolean[100001];
  public static int[] d = new int[100001];

  public static int getSmallestNode() {
    int min_value = INF;
    int index = 0;
    for (int i = 0; i <= n; i++) {
      if (d[i] < min_value && !visited[i]) {
        min_value = d[i];
        index = i;
      }
    }
    return index;
  } // end getSmallestNode

  public static void dijkstra(int start) {
    d[start] = 0;
    visited[start] = true;
    for (int j = 0; j < graph.get(start).size(); j++) {
      d[graph.get(start).get(j).getIndex()] = graph.get(start).get(j).getDistance();
    }

    for (int i = 0; i < n-1; i++) {
      int now = getSmallestNode();
      visited[now] = true;
      for(int j = 0; j < graph.get(now).size(); j++) {
        int cost = d[now] + graph.get(now).get(j).getDistance();
        if (cost < d[graph.get(now).get(j).getIndex()]) {
          d[graph.get(now).get(j).getIndex()] = cost;
        }
      }
    }
  } // end dijkstra

}

우선순위 큐를 활용한 다익스트라 알고리즘 자바 구현

import java.util.*;

class Node implements Comparable<Node> {
  private int index;
  private int distance;

  public Node(int index, int distance) {
    this.index = index;
    this.distance = distance;
  }

  public int getIndex() {
    return this.index;
  }

  public int getDistance() {
    return this.distance;
  }

  @Override
  public int compareTo(Node other) {
    if (this.distance < other.getDistance()) {
      return -1;
    }
    return 1;
  }
}

class Main {

  public static final int INF = (int) 1e9;
  public static int n, m, start;
  public static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
  public static int[] d = new int[100001];

  public static void dijkstra(int start) {
    PriorityQueue<Node> pq = new PriorityQueue<>();
    pq.offer(new Node(start, 0));
    d[start] = 0;
    while(!pq.isEmpty()) {
      Node node = pq.poll();
      int dist = node.getDistance();
      int now = node.getIndex();

      if (d[now] < dist) continue;

      for (int i = 0; i < graph.get(now).size(); i++) {
        int cost = d[now] + graph.get(now).get(i).getDistance();
        if (cost < d[graph.get(now).get(i).getIndex()]) {
          d[graph.get(now).get(i).getIndex()] = cost;
          pq.offer(new Node(graph.get(now).get(i).getIndex(), cost));
        }
      }
    }
  }

  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    m = sc.nextInt();
    start = sc.nextInt();

    for (int i = 0; i <= n; i++) {
      graph.add(new ArrayList<Node>());
    }
    for (int i = 0; i < m; i++) {
      int a = sc.nextInt();
      int b = sc.nextInt();
      int c = sc.nextInt();
      graph.get(a).add(new Node(b, c));
    }

    sc.close();

    Arrays.fill(d, INF);

    dijkstra(start);

    for (int i = 1; i <= n; i++) {
      if (d[i] == INF) {
        System.out.println("INFINITY");
      }
      else {
        System.out.println(d[i]);
      }
    }

  } // end main
}

벨만-포드 알고리즘

벨만-포드 알고리즘은 간선의 가중치가 음의 값을 허용하는 임의의 실수인 경우 사용하는 최단경로 알고리즘이다.

간선을 최대 1개로 사용하는 최단경로, 간선을 최대 2개로 사용하는 최단경로, 이런 식으로 최대 n-1개를 사용하는 최단경로까지 구해간다.

음의 가중치가 있는 유향 그래프

음의 가중치를 갖는 유향 그래프의 최단경로는 벨만-포드 알고리즘을 사용한다. (단, 음의 싸이클 X)

간선을 1개만 사용할 경우의 최단경로

간선을 1개만 사용할 경우의 최단경로를 저장한다.

간선 2개를 사용할 경우의 최단경로

간선 2개를 사용해서 노드에 도달했을 때 최소비용을 계산한다. 기존에 값이 있던 것은 비교하여 더 작은 값을 저장한다. 8보다 -6으로, 11은 12보다 작기에 11로 유지되었다.

간선 3개를 사용할 경우의 최단경로

반복해서 간선의 개수가 n-1일때 최단경로까지 계산하면 최종으로 최단경로를 구할 수 있다.

최단경로