최단경로(shortest path) 문제

네트워크에서 정점 u 와 정점 v 를 연결하는 경로 중에서 간선들의 가중치 합이 최소가되는 경로를 찾는 문제

정점 하나에서 다른 모든 정점으로 가는 최단 거리를 구하는 단일 출발지 문제를 다룬다. 간선 수가 적고 가중치가 모두 1이라면 BFS가 적합하다. 가중치가 0 이상이면 다익스트라, 음수 간선이 있으면 벨만-포드를 고려한다. 음수 순환에 도달할 수 있다면 그 순환을 계속 돌며 경로 비용을 끝없이 낮출 수 있어 최단 거리 자체가 정의되지 않는다.

• 가중치 : 거리, 비용, 시간 등

• 가중치가 없는 그래프 : 간선의 개수가 가장 적은 경로가 최단경로

• 가중치가 있는 그래프 : 시작노드에서 마지막 노드까지 이동할 때 거치는 간선의 가중치의 총합이 최소가 되는 것.

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

네트워크에서 하나의 시작정점에서 모든 다른 정점까지의 최단경로를 찾는 알고리즘

• 간선 가중치가 0 이상이라는 조건을 만족할 때 우선순위 큐 기반 다익스트라를 사용할 수 있다.

• 다익스트라 알고리즘은 0 이상인 가중치가 있는 그래프에서 동작한다. 0 가중치도 허용하지만 음수 간선은 허용하지 않는다.

  • 가장 짧은 임시 거리를 가진 정점을 확정한 뒤 더 짧은 길이 나올 수 없다는 논리가 음수 간선에서는 깨진다.

1. 시작노드를 설정하고 시작 노드부터 특정 노드까지 최소 비용을 저장할 공간과 직전노드를 저장할 공간을 마련한다.

   1. 최소비용을 저장할 공간은 모두 매우 큰 값(무한대 INF 표현)으로 초기화
   2. 시작노드의 최소 비용은 0이고 직전 노드는 자신으로 설정

2. 해당 노드를 통해 방문할 수 있는 노드(아직 방문하지 않은 노드) 중 현재까지 구한 최소 비용이 가작 적은 노드를 선택

   1. 해당 노드를 거쳐 각 노드까지 가는 최소 비용과 현재가지 구한 최소 비용을 비교하여 작은 값을 각 노드의 최소비용으로 갱신
   2. 이때 직전 노드도 같이 갱신

3. 노드의 개수에서 1을 뺀 만큼 반복

//입력 : 가중치 그래프 G, 가중치는 음수가 아님
//출력 : 출력 distance 배열, distance[u]는 v에서 u까지의 최단 거리이다.
//Big O (n^2)
shortest_path(G, v)

s ← {v}
  for 각 정점 w ⊆ G do
    distance[w] <- weight[v][w];
  while 모든 정점이 S에 포함되지 않으면 do
    u <- 집합 S에 속하지 않는 정점 중에서 최소 distance 정점;
    S <- S ∪ {u}
    for u에 인접하고 S에 속하지 않는 각 정점 z do
      if distance[u] + weight[u][z] < distance[z]
         then distance[z] <- distance[u] + weight[u][z]

알고리즘 절차

1. 시작노드 A의 최소비용은 0 직전노드는 A로 초기화

2. 시작노드 A의 최소비용은 0 직전노드는 A로 초기화

2. 방문하지 않은 노드 중 최소비용이 가장 적은 A노드를 선택

3. 방문하지 않은 노드 중 최소비용이 가장 적은 A노드를 선택.

   1. 해당 노드를 거쳐 각 노드까지 가는 비용과 기존에 구한 각 노드의 최소 비용을 비교
   2. A 노드에서 {B, C, E}의 가중치는 각각 {4, 4, 1}
   3. 현재까지 해당 노드의 최소 비용은 INF이므로 B의 최소비용은 4, C의 최소비용은 4, E의 최소비용은 1로 갱신

3. 방문하지 않은 노드 중 최소 비용이 가장 적은 노드 E를 선택

• 선택한 노드를 거쳤을 때 최소 비용을 갱신할 수 있는지 확인.

• 노드 C의 현재 비용은 4, E를 거쳤을 때의 비용은 E의 최소비용(1)과 E → C의 가중치(2)를 합친 값 3

• 현재까지 구한 최소 비용보다 값이 더 작으므로 C의 최소비용3, 직전노드 E 로 수정

• 노드 C의 현재 비용은 4, E를 거쳤을 때의 비용은 E의 최소비용(1)과 E → C의 가중치(2)를 합친 값 3

• 현재까지 구한 최소 비용보다 값이 더 작으므로 C의 최소비용3, 직전노드 E 로 수정

4.방문하지 않은 노드 중 최소비용이 가장 적은 노드 C를 선택.

• 선택한 노드를 거쳤을 때 최소 비용을 갱신할 수 있는지 확인

• 노드 D의 경우 기존 최소비용이 INF(경로 없음)이지만, C를 거치면 최소비용(3) + C → D 의 가중치(8)을 합쳐 11이 되어 INF보다 작다.

• 그러므로 D는 최소비용 11, 직전노드 C로 갱신

• 그러므로 D는 최소비용 11, 직전노드 C로 갱신

5. 방문하지 않은 노드 중 최소비용이 가장 적은 노드 B를 선택

• 선택한 노드를 거쳤을 때 최소 비용을 갱신할 수 있는지 확인

• 확인 할 필요가 없으므로 건너뜀(갱신 없음)

6. 방문하지 않은 노드 중 최소 비용이 가장 적은 노드 D를 방문

• 확인 할 필요가 없으므로 건너뜀(갱신 없음)

import java.util.*;
public class DijkstraAlgorithm {

    public static void main(String[] args) {
        Solution sol = new Solution();
        long[] result = sol.solution(new int[][] {
                {0,1,9},
                {0,2,3},
                {1,0,5},
                {2,1,1}
        }, 0, 3);
        System.out.println(Arrays.toString(result));

        long[] result2 = sol.solution(new int[][] {
                {0,1,1},
                {1,2,5},
                {2,3,1}
        }, 0, 4);
        System.out.println(Arrays.toString(result2));
    }

    private static class Solution {
        public long[] solution(int[][] graph, int start, int n) {
            if (start < 0 || start >= n) throw new IllegalArgumentException("시작 정점 범위 오류");
            return dijkstra(start, n, initAdjList(graph, n));
        }

        private List<List<Node>> initAdjList(int[][] graph, int n) {
            List<List<Node>> adjList = new ArrayList<>(n);

            //인접리스트 초기화
            for (int i = 0; i < n; i ++) {
                adjList.add(new ArrayList<>());
            }

            //graph 정보 인접 리스트로 저장(단방향)
            for (int[] edge : graph) {
                if (edge[2] < 0) throw new IllegalArgumentException("다익스트라에는 음수 간선을 넣을 수 없습니다");
                adjList.get(edge[0]).add(new Node(edge[1], edge[2]));
            }
            return adjList;
        }

        private long[] dijkstra(int start, int n, List<List<Node>> adjList) {
            long[] dist = new long[n];
            Arrays.fill(dist, Long.MAX_VALUE); //도달 불가 표시

            //시작 위치 0으로 초기화
            dist[start] = 0;

            //우선순위 큐를 생성하고 시작 노드를 삽입
            PriorityQueue<Node> priorityQueue = new PriorityQueue<>(Comparator.comparingLong(o -> o.cost));
            priorityQueue.add(new Node(start, 0));

            while(!priorityQueue.isEmpty()) {
                //거리가 가장 짧은 노드를 dequeue
                Node now = priorityQueue.poll();

                //현재노드의 거리 값이 큐에서 거리 값보다 크면, 해당 노드는 이미 방문한 것으로 무시
                if (dist[now.dest] < now.cost) {
                    continue;
                }

                //현재 노드와 인접한 노드들의 거리 값을 계산하여 업데이트
                for (Node next : adjList.get(now.dest)) {
                    //기존에 발견했던 거리보다 더 짧은 거리를 발견했다면 거리 값을 갱신하고 큐에 넣음
                    if (dist[next.dest] > now.cost + next.cost) {
                        dist[next.dest] = now.cost + next.cost;
                        priorityQueue.add(new Node(next.dest, dist[next.dest]));
                    }
                }
            }
            return dist;
        }

        private static class Node {
            int dest;
            long cost;

            public Node(int dest, long cost) {
                this.dest = dest;
                this.cost = cost;
            }
        }
    }
}

벨만-포드 알고리즘(Bellman-ford Algorithm)

• 다익스트라 알고리즘과 마찬가지로 노드에서 노드까지의 최소 비용을 구하는 알고리즘으로, 매 단계마다 모든 간선의 가중치를 다시 확인하여 최소 비용을 갱신하므로 음의 가중치를 가지는 그래프에서도 최단경로를 구할 수 있다.

• 간선의 가중치가 음수인 일반적인 경우 단일 출발지 최단 경로 문제를 해결

  • 가중 방향 그래프 G= (V,E)가 출발점 s와 가중함수 w : E → R 과 함께 주어졌을 때 벨만-포드 알고리즘은 출발점으로부터 도달 가능한 음의 가중치를 갖는 순한이 있는지를 나타내는 논리값을 리턴

• 다익스트라 알고리즘과 마찬가지로 노드에서 노드까지의 최소 비용을 구하는 알고리즘으로, 매 단계마다 모든 가선의 가중치를 다시 확인하여 최소 비용을 갱신하므로 음의 가중치를 가지는 그래프에서도 최단경로를 구할 수 있다.

• 간선의 가중치가 음수인 일반적인 경우 단일 출발지 최단 경로 문제를 해결

  • 가중 방향 그래프 G= (V,E)가 출발점 s와 가중함수 w : E → R 과 함께 주어졌을 때 벨만-포드 알고리즘은 출발점으로부터 도달 가능한 음의 가중치를 갖는 순한이 있는지를 나타내는 논리값을 리턴.

1. 시작 노드를 설정한 다음 시작 노드의 최소비용은 0, 나머지 노드는 INF로 초기화

   • 이후 최소비용을 갱신할 때마다 직전노드도 갱신

2. 과정 2를 마지막으로 한번 더 수행하여 갱신되는 최소 비용이 있는지 확인.

   • 만약 있다면 음의 순환이 있음을 의미

3. 노드의 개수 - 1만큼 연산을 반복

   1. 시작노드에서 갈 수 있는 각 노드에 대해 전체 노드 각각을 거쳐갈 때 현재까지 구한 최소 비용보다 더 적은 최소 비용이 있는지 확인하여 갱신
   2. 최소비용을 갱신할 때 V의 직전 노드 값도 같이 갱신

4. 과정 2를 마지막으로 한번 더 수행하여 갱신되는 최소 비용이 있는지 확인.

   1. 만약 있다면 음의 순환이 있음을 의미

bellman_ford(G, w, s)
 initialize_single_source(G,s)
 for i = 1 to | G.V | - 1
   for 각 간선(u, v) <= G.E
     RELAX(u,v,w)
 for 각 간선(u,v) <= G.E
   if v.d > u.d + w(u.v)
	   return FALSE
return TRUE

알고리즘 절차

1.시작노드 A 기준 최소비용 0, 직전노드 0, 나머지 노드 INF로 초기화

2. 노드 A에서 A를 거쳐 각 노드 {B, C, E}까지 가는 비용중 현재까지 구한 최소 비용보다 적은 값이 있는지 확인하고 현재까지 구한 최소비용보다 적으면 갱신 (간선이 없다면 INF로 계산한다는 것을 주의)

• 최소비용(A)(0) == 최소비용(A)(0) + 간선(A, A)(0) : 갱신하지 않음

• 최소비용(B)(INF) > 최소비용(A)(0) + 간선(A, B)(4) : 최소비용(B)를 INF에서 4로 갱신

• 최소비용(C)(INF) > 최소비용(A)(0) + 간선(A, C)(3) : 최소비용(C)를 INF에서 3로 갱신

• 최소비용(D)(INF) == 최소비용(A)(0) + 간선(A, D)(INF) : 갱신하지 않음

• 최소비용(E)(INF) > 최소비용(A)(0) + 간선(A, E)(-6) : 최소비용(E)를 INF에서 -6로 갱신

3. 노드 A에서 B를 거쳐 각 노드 {D}까지 가는 비용중 현재까지 구한 최소 비용보다 적은 값이 있는지 확인하고 현재까지 구한 최소비용보다 적으면 갱신

• 최소비용(A)(0) < 최소비용(B)(4) + 간선(B, A)(INF) : 갱신하지 않음

• 최소비용(B)(4) == 최소비용(B)(4) + 간선(B, B)(0) : 갱신하지 않음

• 최소비용(C)(3) < 최소비용(B)(4) + 간선(B, C)(INF) : 갱신하지 않음

• 최소비용(D)(INF) > 최소비용(B)(4) + 간선(B, D)(5) : 9로 갱신

• 최소비용(E)(-6) < 최소비용(B)(4) + 간선(B, E)(-6) : 갱신하지 않음

4. 노드 A에서 C를 거쳐 각 노드 {B}까지 가는 비용중 현재까지 구한 최소 비용보다 적은 값이 있는지 확인하고 현재까지 구한 최소비용보다 적으면 갱신 (C를 거쳐 B로 가는 새 경로(5)는 기존 B(4)의 최소 비용보다 크므로 갱신 X)

• 최소비용(A)(0) < 최소비용(C)(3) + 간선(C, A)(INF) : 갱신하지 않음

• 최소비용(B)(4) < 최소비용(C)(3) + 간선(C, B)(2) : 갱신하지 않음

• 최소비용(C)(3) == 최소비용(C)(3) + 간선(C, C)(0) : 갱신하지 않음

• 최소비용(D)(9) > 최소비용(C)(3) + 간선(C, D)(INF) : 갱신하지 않음

• 최소비용(E)(-6) < 최소비용(C)(3) + 간선(C, E)(INF) : 갱신하지 않음

5. 노드 A에서 D를 거쳐서 가는 방법은 없으므로 갱신하지 않음

6. 노드 A에서 E를 거쳐 각 노드까지 가는 최소비용을 갱신. 모든 최단 경로에 대해 노드의 최소비용을 체크했으므로, 벨만-포드 알고리즘의 첫번째 반복이 끝난다.

• 최소비용(A)(0) < 최소비용(E)(-6) + 간선(E, A)(INF) : 갱신하지 않음

• 최소비용(B)(4) < 최소비용(E)(-6) + 간선(E, B)(INF) : 갱신하지 않음

• 최소비용(C)(3) > 최소비용(E)(-6) + 간선(E, C)(2) : -4로 갱신

• 최소비용(D)(9) > 최소비용(E)(-6) + 간선(E, D)(INF) : 갱신하지 않음

• 최소비용(E)(-6) < 최소비용(E)(-6) + 간선(E, E)(0) : 갱신하지 않음

1. 위해서 했던 과정을 노드개수 -1 번 반복하므로 1~6단계를 4번 더 반복

2. 위해서 했던 과정을 노드개수 -1 번 반복하므로 1~6단계를 4번 더 반복

import java.util.Arrays;

public class BellManFord {
    private static final long INF = Long.MAX_VALUE;

    // 정점 번호는 0부터 n-1까지이며, 간선은 {from, to, weight} 형식이다.
    public static long[] shortestPaths(int n, int[][] edges, int start) {
        if (n < 1 || start < 0 || start >= n) {
            throw new IllegalArgumentException("정점 수 또는 시작점 범위 오류");
        }
        long[] dist = new long[n];
        Arrays.fill(dist, INF);
        dist[start] = 0;

        for (int pass = 1; pass < n; pass++) {
            boolean changed = false;
            for (int[] edge : edges) {
                int from = edge[0], to = edge[1], weight = edge[2];
                if (from < 0 || from >= n || to < 0 || to >= n) {
                    throw new IllegalArgumentException("간선 정점 범위 오류");
                }
                if (dist[from] == INF) continue;
                long candidate = dist[from] + weight;
                if (candidate < dist[to]) {
                    dist[to] = candidate;
                    changed = true;
                }
            }
            if (!changed) break;
        }

        for (int[] edge : edges) {
            int from = edge[0], to = edge[1], weight = edge[2];
            if (dist[from] != INF && dist[from] + weight < dist[to]) {
                throw new IllegalArgumentException("시작점에서 도달 가능한 음수 순환");
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int[][] edges = {{0,1,7}, {0,2,5}, {2,3,3}, {3,4,-6}};
        System.out.println(Arrays.toString(shortestPaths(5, edges, 0)));

        int[][] negativeCycle = {{0,1,1}, {1,2,-3}, {2,1,1}};
        try {
            shortestPaths(3, negativeCycle, 0);
        } catch (IllegalArgumentException error) {
            System.out.println(error.getMessage());
        }
    }
}

첫 예제의 결과는 [0, 7, 5, 8, 2]다. 두 번째는 1→2→1의 비용이 -2인 음수 순환이 시작점 0에서 도달 가능하므로 최단 거리가 정의되지 않는다. 원래 실습 입력에도 3→4→5→3의 비용 3-6+2=-1인 음수 순환이 있었는데 이를 탐지하지 않고 거리를 출력했다. 도달할 수 없는 정점의 결과는 Long.MAX_VALUE로 남는다.

다익스트라 알고리즘, 벨만 포드 알고리즘 차이

두 코드에서 공통 핵심 연산은 완화(relaxation)다. 현재 dist[u]를 알고 있을 때 간선 (u,v,w)를 거쳐 가는 후보 dist[u]+w가 dist[v]보다 작으면 갱신한다. 다익스트라는 우선순위 큐에서 꺼낸 가장 작은 현재 거리를 기준으로 완화한다. dist[now.dest] < now.cost이면 같은 정점의 더 나쁜 옛 큐 항목이므로 버린다. 예제의 0→2(3)→1(1)은 비용 4로 처음 발견한 0→1(9)를 갱신한다. 음수 간선이 없으므로 꺼낸 최소 거리보다 더 싼 경로가 뒤늦게 나타나지 않는다. 인접 리스트와 힙의 시간은 O((V+E) log V), 저장 공간은 O(V+E)다.

벨만-포드는 모든 간선을 최대 V-1회 반복 완화한다. 간선 한 개가 경로의 끝을 하나 연장한다고 보면, k회 반복 뒤에는 최대 k개 간선으로 도달 가능한 경로의 비용이 반영된다. 음수 순환이 없는 단순 최단 경로는 최대 V-1개 간선을 사용한다. 그 이후에도 비용을 더 줄일 수 있으면 시작점에서 도달 가능한 음수 순환이 있다. 단, dist[u]가 무한대인 간선으로는 완화하지 않아야 도달할 수 없는 곳의 음수 순환을 잘못 신고하지 않는다. 시간은 O(VE), 거리 배열 공간은 O(V)이다.

실제 경로까지 출력하려면 완화할 때 parent[v]=u도 저장하고 목적지에서 역순으로 따라가면 된다. 도달 불가 노드는 무한대 표식을 그대로 두며, 시작점에서 도달 가능한 음수 순환이 있다면 해당 영향을 받는 경로의 최단값을 일반 숫자로 제시해서는 안 된다. 위 예제들은 long 거리로 단순한 int 합의 오버플로 위험을 줄였지만 극단적으로 큰 가중치와 경로 길이에 대한 별도 범위 검증은 필요하다.

	목적	장 단점 및 특성	시간 복잡도
다익스트라 알고리즘	출발 노드부터 도착 노드들까지의 최단 경로 찾기	음의 가중치를 가지는 그래프에서 최단 경로를 구할 수 없다(그리디 방식)	O(V^2), 우선순위 큐로 개선하면 O(E*logV)
벨만-포드 알고리즘	출발 노드부터 도착노드들까지의 최단 경로 찾기	음의 가중치를 가지는 그래프에서 최단 경로를 구할 수 있고, 음의 순환도 감지할 수 있다.	O(V*E)

References

C 언어로 쉽게 풀어쓴 자료 구조

코딩 테스트 완전 전복

Introduction to algorithms

	목적	장 단점 및 특성	시간 복잡도
다익스트라 알고리즘	출발 노드부터 도착 노드들까지의 최단 경로 찾기	음의 가중치를 가지는 그래프에서 최단 경로를 구할 수 없다(그리디 방식)	O(V^2), 우선순위 큐로 개선하면 O(E*logV)
벨만-포드 알고리즘	출발 노드부터 도착노드들까지의 최단 경로 찾기	음의 가중치를 가지는 그래프에서 최단 경로를 구할 수 있고, 음의 순환도 감지할 수 있다.	O(V*E)