15. 그래프 최단경로(다익스트라, 벨만-포드)

최단경로(shortest path) 문제

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

• 가중치 : 거리, 비용, 시간 등
• 가중치가 없는 그래프 : 간선의 개수가 가장 적은 경로가 최단경로
• 가중치가 있는 그래프 : 시작노드에서 마지막 노드까지 이동할 때 거치는 간선의 가중치의 총합이 최소가 되는 것.

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

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

• 가중치가 있는 알고리즘은 대부분 다익스트라 알고리즘을 사용한다고 보면된다.
• 다익스트라 알고리즘은 양의 가중치만 있는 그래프에서만 동작하므로 음의 가중치가 있는 그래프에서 제대로 동작하지 않는다.
  • 다익스트라 알고리즘은 한 번 방문한 노드는 다시 방문하지 않는다. 그러므로 음의 가중치가 있는 그래프에서는 제대로 작동하지 않는것.

1. 시작노드를 설정하고 시작 노드부터 특정 노드까지 최소 비용을 저장할 공간과 직전노드를 저장할 공간을 마련한다.
   • 최소비용을 저장할 공간은 모두 매우 큰 값(무한대 INF 표현)으로 초기화
   • 시작노드의 최소 비용은 0이고 직전 노드는 자신으로 설정
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노드를 선택

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

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로 갱신

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

• 선택한 노드를 거쳤을 때 최소 비용을 갱신할 수 있는지 확인
• 확인 할 필요가 없으므로 건너뜀(갱신 없음)

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

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

import java.util.*;
public class DijkstraAlgorithm {

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] 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));

        int[] 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 int[] solution(int[][] graph, int start, int n) {
            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) {
                adjList.get(edge[0]).add(new Node(edge[1], edge[2]));
            }
            return adjList;
        }

        private int[] dijkstra(int start, int n, List<List<Node>> adjList) {
            int[] dist = new int[n];
            Arrays.fill(dist, Integer.MAX_VALUE); //INF 로 초기화

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

            //우선순위 큐를 생성하고 시작 노드를 삽입
            PriorityQueue<Node> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(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;
            int cost;

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

 

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

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

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

1. 시작 노드를 설정한 다음 시작 노드의 최소비용은 0, 나머지 노드는 INF로 초기화
   • 이후 최소비용을 갱신할 때마다 직전노드도 갱신
2. 노드의 개수 - 1만큼 연산을 반복
   • 시작노드에서 갈 수 있는 각 노드에 대해 전체 노드 각각을 거쳐갈 때 현재까지 구한 최소 비용보다 더 적은 최소 비용이 있는지 확인하여 갱신
   • 최소비용을 갱신할 때 V의 직전 노드 값도 같이 갱신
3. 과정 2를 마지막으로 한번 더 수행하여 갱신되는 최소 비용이 있는지 확인.
   • 만약 있다면 음의 순환이 있음을 의미

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번 더 반복

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BellManFord {

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

        int[] result2 = sol.solution2(new int[][] {
                {1,2,7},
                {1,3,5},
                {1,4,3},
                {3,4,3},
                {3,5,3},
                {4,2,3},
                {4,5,-6},
                {5,3,2},
        }, 1, 7);
        System.out.println(Arrays.toString(result2));
    }
    private static class Solution {
        private static final int INF = Integer.MAX_VALUE;

        public int[] solution(int[][] graph, int start, int n) {
            List<List<Node>> adjList = initAdjList(graph, n);

            int[] dist = new int[n];
            Arrays.fill(dist, INF);
            dist[start] = 0;

            //정점 수 만큼 반복
            for (int v = 1; v <= n; v++) {
                //모든 간선을 순회
                for (Node node : adjList.get(v)) {
                    if (dist[node.from] == INF) {
                        continue;
                    }

                    if (dist[node.to] > dist[node.from] + node.cost) {
                        dist[node.to] = dist[node.from] + node.cost;
                    }
                }
            }
            return dist;
        }
        private int[] solution2(int[][] graph, int start, int n) {
            List<List<Node>> adjList = initAdjList(graph, n);

            int[] dist = new int[n];
            Arrays.fill(dist, INF);
            dist[start] = 0;

            //정점 수 만큼 반복
            for (int v = 1; v <= n; v++) {
                //모든 간선을 순회
                for (Node node : adjList.get(v)) {
                    if (dist[node.from] != INF) {
                        dist[node.to] = Math.min(dist[node.to], dist[node.from] + node.cost);
                    }
                }
            }
            return dist;
        }
        private List<List<Node>> initAdjList(int[][] graph, int n) {
            List<List<Node>> adjList = new ArrayList<>();

            for (int i = 0; i <= n; i ++) {
                adjList.add(new ArrayList<>());
            }

            for (int[] edge : graph) {
                adjList.get(edge[0]).add(new Node(edge[0], edge[1], edge[2]));
            }
            return adjList;
        }

        private static class Node {
            int from;
            int to;
            int cost;

            public Node(int from, int to, int cost) {
                this.from = from;
                this.to = to;
                this.cost = cost;
            }
        }
    }
}

 

 

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

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

 

 

References

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

코딩 테스트 완전 전복

Interotuction to algorithms