최단 경로 알고리즘

1. 최단 경로 알고리즘이란?

최단 경로 알고리즘은 그래프에서 한 정점에서 다른 정점까지 가는 데 필요한 최단 거리를 찾는 알고리즘입니다. 여기서 ‘최단’의 의미는 경로 상의 가중치 합이 가장 작다는 뜻입니다. 예를 들어, 지도에서 두 도시를 최단 거리로 연결하는 방법을 찾는 것이 최단 경로 문제라고 볼 수 있습니다.

방금 제가 풀고 있던 이 문제: https://www.acmicpc.net/problem/16928 에서의 '정점'은 게임판의 칸이 될 것이며, 각 칸마다 이동하는 것이 경로를 통해 이동하는 상황이 되는 것입니다. 다만, 이 문제에서는 각 경로의 가중치가 모두 1로 동일한 상황이며, 이 경우에는 어떤 알고리즘으로 푸는 게 적합한지 글의 마지막 부분에 언급하도록 하겠습니다.

 

2. 대표적인 최단 경로 알고리즘

가중치가 있는 그래프에서 최단 경로를 찾기 위해 많이 사용하는 알고리즘 세 가지는 다음과 같습니다.

1. 다익스트라 알고리즘: 가중치가 양수인 그래프에서 출발점에서 다른 모든 정점까지의 최단 경로를 찾을 때 사용됩니다. 최단 경로가 확정된 노드부터 순차적으로 탐색하며, 각 노드의 최단 경로를 갱신하는 방식입니다.
2. 플로이드-와샬 알고리즘: 모든 정점 쌍 간의 최단 경로를 구하는 데 사용됩니다. 간선의 가중치가 양수든 음수든 상관없으며, 음수 사이클이 없는 그래프에서 유효하게 작동합니다.
3. 벨만-포드 알고리즘: 음수 가중치가 있는 그래프에서도 최단 경로를 찾을 수 있는 알고리즘입니다. 다익스트라와 달리 모든 간선을 여러 번 검사하여 최단 경로를 업데이트하는 방식입니다.

다익스트라 알고리즘의 동작 원리

다익스트라 알고리즘을 이해하기 위해 예시를 살펴보겠습니다.

먼저 다익스트라 알고리즘의 핵심 아이디어는 아래와 같습니다.

• 출발점에서 다른 정점까지의 최단 거리를 점차적으로 업데이트하면서 최종 최단 경로를 찾습니다.
• ‘방문한 노드’와 ‘방문하지 않은 노드’를 나누고, 현재 방문한 노드에서 가장 가까운 노드를 선택하여 거리를 갱신합니다.
  • 다익스트라 알고리즘은 이러한 원리로 최단경로를 찾기 때문에, 그리디 알고리즘으로 분류됩니다.

예시

 

• 각 선의 숫자는 두 노드 사이의 가중치를 나타냅니다.
• 여기서 A에서 다른 모든 노드까지 최단 거리를 구하고 싶다고 가정하겠습니다.

다익스트라 알고리즘을 적용하는 단계:

1. 초기화: 출발 노드 A의 거리를 0으로 설정하고, 다른 모든 노드는 무한대로 설정합니다.
2. 가장 가까운 노드 선택: 현재 방문하지 않은 노드 중 출발점과의 거리가 가장 짧은 노드를 선택합니다. 처음에는 A가 선택되겠죠.
3. 거리 갱신: 선택된 노드 A에서 직접 연결된 노드 B와 D의 거리를 확인하고, A를 경유하는 거리가 더 짧다면 거리 값을 갱신합니다.
   • 예를 들어, A에서 B로 가는 거리는 5이므로, B까지의 거리를 5로 갱신합니다.
   • A에서 D로 가는 거리는 3이므로, D까지의 거리를 3으로 갱신합니다.
4. 반복: 방문하지 않은 노드 중 가장 가까운 노드를 계속 선택하고, 연결된 노드들의 거리를 갱신합니다. 모든 노드가 방문될 때까지 반복합니다.
5. 결과: 모든 노드에 대해 출발점 A에서부터의 최단 거리가 구해집니다.

 

다익스트라 알고리즘의 코드 구현 (Java 예시)

import java.util.*;

public class Dijkstra {
    static class Edge {
        int destination, weight;
        Edge(int destination, int weight) {
            this.destination = destination;
            this.weight = weight;
        }
    }
    
    public static void dijkstra(List<List<Edge>> graph, int source) {
        int[] distances = new int[graph.size()];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[source] = 0;
        
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        pq.add(new Edge(source, 0));
        
        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            for (Edge edge : graph.get(current.destination)) {
                int newDist = distances[current.destination] + edge.weight;
                if (newDist < distances[edge.destination]) {
                    distances[edge.destination] = newDist;
                    pq.add(new Edge(edge.destination, newDist));
                }
            }
        }
        
        System.out.println("출발점에서 각 노드까지의 최단 거리:");
        for (int i = 0; i < distances.length; i++) {
            System.out.println("노드 " + i + "까지의 거리: " + distances[i]);
        }
    }
    
    public static void main(String[] args) {
        int n = 6; // 노드의 수
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 예시 그래프 구축
        graph.get(0).add(new Edge(1, 5)); // A->B (가중치 5)
        graph.get(0).add(new Edge(3, 3)); // A->D (가중치 3)
        graph.get(1).add(new Edge(2, 2)); // B->C (가중치 2)
        graph.get(1).add(new Edge(4, 1)); // B->E (가중치 1)
        graph.get(2).add(new Edge(5, 4)); // C->F (가중치 4)
        graph.get(3).add(new Edge(4, 6)); // D->E (가중치 6)
        graph.get(4).add(new Edge(5, 7)); // E->F (가중치 7)
        
        dijkstra(graph, 0); // A에서 시작
    }
}

위의 코드에서, dijkstra 함수는 그래프를 받아 출발점에서 각 노드까지의 최단 거리를 계산합니다. 우선순위 큐(Priority Queue)를 사용하여 최단 거리를 효율적으로 관리하며 업데이트합니다.

 

참고: 우선순위 큐를 사용하는 이유

우선순위 큐를 사용하면, 우선순위 큐에서 가장 우선순위가 높은 요소(여기서는 가장 짧은 거리의 노드)를 빠르게 꺼낼 수 있습니다(시간 복잡도 O(logN)). 우선순위 큐를 사용하지 않고 단순히 배열이나 리스트를 사용해 매번 최단 거리를 가진 노드를 찾으려면 모든 노드를 일일이 확인해야 하므로 시간 복잡도가 높아집니다(O(N)).

 

다익스트라 알고리즘의 시간 복잡도

다익스트라 알고리즘의 시간 복잡도는 그래프의 표현 방식에 따라 다릅니다. 일반적으로 우선순위 큐를 사용하는 경우, 시간 복잡도는 O(Elog⁡N)입니다. 여기서 E는 간선의 수, N은 노드의 수입니다.

간선에 가중치가 없는 그래프의 최단 경로 알고리즘

가중치가 없는 그래프에서 최단 경로를 찾는 가장 효율적인 알고리즘은 BFS입니다.

BFS는 시작점에서 가장 가까운 노드부터 차례로 탐색하며, 이미 방문한 노드는 다시 방문하지 않습니다. 노드를 탐색할 때마다 거리를 1씩 증가시키므로, 가중치가 없는 그래프에서는 최단 경로를 보장할 수 있습니다. 이 경우의 최단 경로는 시작 정점에서 도착 정점까지 거치는 간선의 개수가 최소인 경로를 의미하겠죠!

BFS는 시작점에서 특정 목표 노드까지의 최단 거리를 구하는 데 적합하지만, 특정한 모든 최단 경로(모든 경로 중 최단)를 구하는 경우에는 모든 경로를 직접 탐색해야 합니다.

BFS를 사용한 최단 경로 예제 (Java)

import java.util.*;

public class BFSExample {
    public static int bfsShortestPath(Map<Integer, List<Integer>> graph, int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        Map<Integer, Integer> distance = new HashMap<>();
        queue.add(start);
        distance.put(start, 0);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (node == end) return distance.get(node); // 최단 거리 도착

            for (int neighbor : graph.get(node)) {
                if (!distance.containsKey(neighbor)) {
                    queue.add(neighbor);
                    distance.put(neighbor, distance.get(node) + 1);
                }
            }
        }
        return -1; // 경로가 없는 경우
    }
}

 

참고 블로그:

1. https://velog.io/@ksi05503/heap%EA%B3%BCheapify 

2. https://dongwooblog.tistory.com/180