알고리즘 - 최단 경로 알고리즘

최단 경로 알고리즘

---

최단 경로 알고리즘이란 가중 그래프 상의 두 정점을 연결하는 가장 짧은 경로를 찾는 방법입니다.

 

이러한 최단 경로 알고리즘은 지도로 최단 경로를 찾거나 , 네트워크 구축 시 비용을 최소화하는 데 사용되곤 합니다.

 

다양한 사용처가 있는 만큼 알아두면 좋은 알고리즘입니다.

 

 

최단 경로 알고리즘 종류

---

📌 다익스트라 (Dijkstra)

---

 

에츠허르 다익스트라가 고안한 유명한 알고리즘입니다.

 

다익스트라 알고리즘은 그래프의 방향 유무와 상관없이 하나의 정점으로부터 다른 모든 정점으로의 최단 경로를 구할 수 있습니다. 

 

다만, 간선에 음의 가중치가 존재하면 사용할 수 없기 때문에 음의 가중치를 이용해야 한다면 다익스트라 외의 다른 알고리즘을 사용하면 됩니다. 

 

🔨 구현

---

그리디와 DP가 혼합된 형태이며, 인접 행렬과 인접 리스트로 구현할 수 있습니다.

 

기본적으로 O(V^2)의 시간복잡도를 가지지만, 우선순위 큐를 이용하면 O(ElogV)의 시간복잡도를 가집니다.

 

우선순위 큐로 다익스트라 알고리즘은 다음과 같은 과정을 거칩니다.

 

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 *  알고리즘 흐름
 *  1. 출발점으로부터의 최단거리를 저장할 배열 선언 
 *  2. 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 INF로 초기화
 *  3. 우선순위 큐를 이용하여 최단 거리 탐색 시작
 *  3-1. 우선순위 큐에서 가중치가 가장 작은 간선 가져오기
 *  3-2. 간선이 향하는 노드가 이미 방문한 노드라면 통과
 *  3-3. 간선이 향하는 노드를 현재 노드로 삼고, 현재 노드 기준 인접 노드의 최단 거리를 Min(인접 노드 최단 거리, 현재 노드 최단 거리 + 간선 가중치)로 갱신
 *  3-4. 인접노드들을 우선순위 큐에 넣기
 *  3-5. 현재 노드 방문 처리
 *  4. 3번 과정을 반복
 */
public class Dijkstra {
	static int V;
	static boolean[] visited;
	static int[] distance;
	static ArrayList<Edge>[] edges;

	public static void dijkstra(int start) {

		// 1. 출발점으로부터 최단거리를 저장할 배열 선언
		// 배열은 0부터 시작하므로 편의 상 V + 1 크기로 잡음
		distance = new int[V + 1];

		// 2. 최단거리 배열의 출발점은 0, 그 외는 INF 값으로 초기화
		for (int i = 1; i <= V; i++) {
			distance[i] = Integer.MAX_VALUE;
		}

		distance[start] = 0;

		PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));

		pq.add(new Edge(1, 0));  // 자기 자신을 향하는 간선의 가중치는 0

		/**
		 *  3. 최단거리 탐색 시작
		 */
		while (!pq.isEmpty()) {
			// 3-1. 최단거리 간선을 꺼내 현재 노드로 삼기
			Edge cur = pq.poll();

			ArrayList<Edge> adj = edges[cur.to]; // 현재 노드의 인접 노드로 향하는 간선들

			for (Edge edge : adj) {
				if (visited[edge.to]) { // 이미 방문한 노드일 경우 통과
					continue;
				}

				// 3-2. 인접 노드들의 최단 거리를 업데이트
				distance[edge.to] = Math.min(distance[edge.to], distance[cur.to] + edge.weight);

				// 3-3. 인접 노드를 우선 순위큐에 삽입
				pq.add(new Edge(edge.to,distance[edge.to]));
			}

			// 3-4. 현재 노드를 방문 처리
			visited[cur.to] = true;
		}
	}

	static class Edge {
		int to;
		int weight;

		public Edge(int to, int weight) {
			this.to = to;
			this.weight = weight;
		}
	}
}

 

 

📌 벨만-포드 (Bellman-Ford)

---

기본적인 것은 앞의 다익스트라와 같습니다.

 

차이점이 있다면, 벨만-포드는 음의 가중치를 가진 간선이 있더라도 사용할 수 있다는 점이 다익스트라와 다릅니다.

 

다만, 음수 사이클이 존재하면 정상적으로 작동하지 않습니다. 

 

🔨 구현

---

시간 복잡도는 모든 정점의 모든 간선을 확인하다 보니 다익스트라에 비해 느린 O(VE)의 시간 복잡도를 가집니다.

 

/**
 *  알고리즘 흐름
 *  0. 출발 노드를 설정 후, 최단 거리 배열을 초기화
 *  0-1. 출발 노드는 0, 그 외의 노드는 INF
 *  1. 전체 간선을 돌면서, 최단 거리 배열을 업데이트
 *  1-1. 출발지의 최단 경로가 INF라면, 아무것도 하지 않고 통과
 *  1-2. 출발지의 최단 경로가 INF가 아니라면, 출발지 최단 경로 값 + 간선의 가중치를 도착지의 최단경로 값과 비교해 작은 값으로 갱신
 *  2. 1번 과정을 노드 수 만큼 반복
 *  3. 노드 수보다 1 만큼 더 돌면서 음수 사이클이 있는지 체크
 *  3-1. 노드 수보다 더 돌았을 때, 최단 거리에 변경이 있다면 음수 사이클이 존재하는 것
 */

public class BellmanFord {

   static int[] distance;

   static int V;
   static int E;

   static Edge[] edges;


   public static void bellman_ford(int start) {

      /**
       * 0. 초기화 과정
       */

      distance = new int[V + 1];

      for (int i = 1; i <= V; i++) {
         distance[i] = Integer.MAX_VALUE;
      }

      distance[start] = 0;

      // 음수 사이클 체크
      boolean isMinusCycle = false;

      /**
       * 1. V * E 만큼 간선을 돌면서 갱신
       */
      for (int i = 0; i < V + 1; i++) {
         for (int j = 0; j < E; j++) {

            Edge cur = edges[j];

            if (distance[cur.from] == Integer.MAX_VALUE) {
               continue;
            }

            if (distance[cur.to] > distance[cur.from] + cur.weight) {
               distance[cur.to] = distance[cur.from] + cur.weight;

               if (i == V) {
                  isMinusCycle = true;
               }
            }
         }
      }

      if (isMinusCycle) {
         System.out.println("음수 사이클 발생");
      }
   }

   static class Edge {
      int from;
      int to;
      int weight;
   }
}

 

 

📌 플로이드-워셜 (Floyd-Warshall)

---

앞의 두 알고리즘이 한 정점에서 모든 정점의 최단거리를 구하는 거였다면, 플로이드-워셜 알고리즘은 모든 정점 간의 최단 경로를 구하는 알고리즘입니다.

 

벨만-포드와 마찬가지로 음의 가중치를 가지는 간선이 있더라도 사용할 수 있고, 음수 사이클이 있다면 정상 작동하지 않습니다. 

 

 

🔨 구현

---

모든 경로를 구하다 보니 O(V^3)의 시간복잡도를 가지고 있습니다.

 

플로이드-워셜은 다음과 같은 원리를 이용해 구현합니다.

 

 

• s : 출발 노드 
• e : 도착 노드
• m : 출발노드에서 도착 노드까지 가는데 거치는 중간 노드
• s에서 e로 가는 최단 거리 = s에서 m으로 가는 최단 거리 + m에서 e로 가는 최단 거리

 

위와 같은 원리로 반복문을 3번 중첩시켜서 구현할 수 있습니다. 

 

/**
 * 알고리즘 흐름
 * 1. 최단 거리 배열 초기화
 * 1-1. 자기 자신에게 가는 경로는 0, 그 외의 모든 경로는 INF로 초기화
 * 2. 모든 노드를 돌면서 인접 노드로 향하는 간선 가중치를 최단 거리 배열에 업데이트
 * 3. s ~ e = (s ~ m) + (m ~ e) 로 최단 거리 구하기
 * 4. 음수 사이클이 존재하는지 확인
 * 4-1. 자기 자신의 최단 거리가 음수라면 음수 사이클이 존재
 */
public class FloydWarshall {

   static int[][] distance;
   static int V;

   static Edge[] edges;


   /**
    * 1. 초기화
    */
   public static void init() {
      distance = new int[V + 1][V + 1];

      for (int i = 1; i <= V; i++) {
         for (int j = 1; j <= V; j++) {
            if (i != j) {
               distance[i][j] = Integer.MAX_VALUE;
            }
         }
      }
   }

   public static void floyd_warshall() {

      init();

      /**
       *     2. 인접한 노드로 향하는 간선 가중치를 최단 거리 배열에 업데이트
       */
      for (Edge edge : edges) {
         distance[edge.from][edge.to] = edge.weight;
      }

      /**
       * 3. s ~ e = (s ~ m) + (m ~ e) 로 최단 거리 구하기
       */
      for (int m = 1; m <= V ; m++) { // 가운데 노드
         for (int s = 1; s <= V ; s++) { // 출발 노드
            for (int e = 1; e <= V ; e++) { // 도착 노드

               // (s~m)이나 (m~e)의 최단거리 값이 INF 라면, 연결되어있지 않음을 의미
               if (distance[s][m] != Integer.MAX_VALUE
                  && distance[m][e] != Integer.MAX_VALUE) {
                  distance[s][e] = Math.min(distance[s][e], distance[s][m] + distance[m][e]);
               }
            }
         }
      }

      /**
       * 4. 음수 사이클 확인
       */

      for (int i = 1; i <= V; i++) {
         if (distance[i][i] < 0) {
            System.out.println("음수 사이클이 존재");
            return;
         }
      }

   }

   static class Edge {
      int from;
      int to;
      int weight;
   }

}

 

 

요약

---

다익스트라는 그리디를 이용하여 간선을 돌고, 벨만-포드는 모든 간선을 돌고, 플로이드 워셜은 두 경로사이의 경유지를 통해 최단 거리를 구한다고 보면 됩니다.

 

음수 간선이 있는게 아닌 이상, 다익스트라를 사용하는게 더 좋습니다.