[개념정리] Shortest Path(최단 경로) 알고리즘

[jusung-c]

최단 경로(Shortest Path) 알고리즘

최단 거리를 구해주는 알고리즘은 대표적으로 6가지이다.
이 중 코딩테스트에서 주로 알아야 하는 것은 2가지이다.

BFS

첫 번째 방법은 앞서 배웠던 BFS이다.

탐색(Search) = 시작점에서 간선을 0개 이상 사용해서 갈 수 있는 정점들은 무엇인가?

탐색 중 DFS, BFS가 있었고, 그 중 BFS는 탐색과 더불어 사이드 이펙트로 최소 이동 횟수를 계산할 수 있었다.
여기서 한번의 이동은 간선의 가중치가 1이라고 생각한 경우이다.

따라서 BFS의 경우는 간선의 가중치가 1인 그래프에서만 적용할 수 있는 방법으로 한 정점에서 시작해 모든 정점까지의 최단 거리를 계산할 수 있는 알고리즘이다.

시간 복잡도는 모든 정점과 모든 간선을 순회하므로 O(V+E)이다.

다익스트라 알고리즘

입력

• Graph G(V, E) := Nonnegative-Weighted Graph
  • 모든 간선의 가중치가 음수가 아니어야 한다. -> 매우 중요!!
• Start Vertex S / Vertices {S1, ...}
  • BFS와 마찬가지로 시작점이 필요하다.
  • BFS와 마찬가지로 멀티 소스 탐색이 가능하다.

출력

• 시작점에서 모든 점까지의 최단 거리

시간 복잡도

• O(E logV)

다익스트라 알고리즘을 적용하기 위해 필요한 정보

1. dist[i] := 시작점에서 i번 정점까지의 가능한 최단 거리
2. 자료구조 D := {(v, d) | 시작점에서 v까지 d만에 갈 수 있음을 확인했다.}
   • 예를 들어 (1, 21)이면 시작점에서 1번 정점까지 21만에 갈 수 있음을 확인한 상태

1. dist 배열 초기화
- 모든 i에 대해서 dist 배열을 초기화한다.
- 시작점의 경우엔 0으로 넣고 나머지는 아직 모르기 때문에 무한값을 넣어준다.
- 자료구조 D에 시작점 (S, 0)을 넣는다.

2. 자료구조 D가 비었는지 판단

3. D에서 가장 작은 d를 가진 자료 (v, d)를 뽑는다.

4. 뽑은 (v, d)가 기존의 dist[v]와 비교해서 가치가 있는지 판단한다.
- 이전에 갱신했던 dist[v]보다 뽑은 (v, d)의 d가 크다면 가치가 있는 것.

5. 뽑은 (v, d)를 통해 새로운 정보를 자료구조 D에 추가
- v에서 w로 가는 간선이 있다고 가정할 때, (v, d)의 d값에 + v에서 w까지의 거리 c를 더해주면 이동 비용이 계산된다.
- 이 d + c 값이 기존에 계산된 dist[w]보다 작은 경우 가치가 있는 것이므로 그 때 갱신해준다.
- 갱신하면 (w, d+c)가 될 것이고, 이것을 자료구조 D에 넣어준다.

다익스트라 예제 흐름

1. dist 배열을 초기화하고, 시작점을 D에 넣어준다.

2. D가 비어있는지 확인 -> 비어있지 않다.

3. D에서 d가 가장 작은 값인 (1, 0)을 선택

4. (1, 0)과 dist[1]의 값 비교해보니 둘 다 0으로 같으므로 가치가 있음.

5. 가치가 있으므로 1번과 연결된 간선들을 확인

   • (2, 10) 간선: 0+10은 dist2보다 작으므로 갱신한 뒤 (2, 10)을 D에 추가
   • (3, 23) 간선: 0+23은 dist3보다 작으므로 갱신한 뒤 (3, 23)을 D에 추가

6. D에서 d가 가장 작은 값인 (2, 10) 선택

7. (2, 10)과 dist[2]의 값 비교해보니 둘 다 10으로 같으므로 가치가 있음

8. 가치가 있으므로 2번과 연결된 간선들을 확인

   • (5, 36) 간선: 10+36은 dist5보다 작으므로 갱신한 뒤 (5, 36)을 D에 추가
   • (3, 7) 간선: 10+7은 dist3보다 작으므로 17로 갱신한 뒤 (3, 17)을 D에 추가

9. D에서 d가 가장 작은 값인 (3, 17) 선택

10. (3, 17)과 dist[3]의 값을 비교해보니 둘 다 17로 같으므로 가치가 있음

11. 가치가 있으므로 3번과 연결된 간선들을 확인

    • (5, 15) 간선: 17+15은 dist5보다 작으므로 32로 갱신한 뒤 (5, 32)을 D에 추가
    • (4, 1) 간선: 17+1은 dist4보다 작으므로 갱신한 뒤 (4, 18)을 D에 추가

12. D에서 d가 가장 작은 값인 (4, 18) 선택
13. (4, 18)과 dist[4]의 값을 비교해보니 둘 다 18로 같으므로 가치가 있음
14. 가치가 있으므로 4번과 연결된 간선들을 확인
    • (5, 4) 간선: 18+4은 dist5보다 작으므로 22로 갱신한 뒤 (5, 22)을 D에 추가

15. D에서 d가 가장 작은 값인 (5, 22)은 가치는 있지만 연결된 간선이 없으므로 패쓰
16. D에서 d가 가장 작은 값인 (3, 23)은 dist[3]인 17보다 크므로 가치가 없다. 패쓰
17. 마찬가지로 (5, 32), (5, 46) 모두 가치 없으니까 패쓰
18. D가 비었으므로 종료

시간복잡도를 알기 위해서 증명하는 과정은 너무 복잡하고, 어떤 자료구조로 구현하냐에 따라 달라지기 때문에 일단은 그냥 대충만 이해하고 외우자.

• 모든 정점은 단 한 번씩 가치가 있는 v로 등장한다. -> Priority Queue의 경우 넣거나 빼는데 O(log V)가 걸린다.
• 한번 v로 뽑히면 v에 연결된 정점들을 탐색한다. -> E
• 따라서 O(E logV)

다익스트라 구현하기

1. dist 배열 초기화 및 시작점 자료구조에 넣기

    static void dijkstra(int start) {
        // 모든 정점까지에 대한 거리를 무한대로 초기화 
        for (int i = 1; i <= N; i++) dist[i] = Integer.MAX_VALUE;  // 문제의 조건에 따라 int 범위를 넘어갈 경우엔 그에 맞게 설정해줘야 한다. 반드시 최댓값보다 큰 값으로 초기화 해주자
        
        // 최소 힙 생성(우선순위큐)
        // 방법 1)
        PriorityQueue<Info> pq = new PriorityQueue<Info>(Comparator.comparing(o -> o.dist));
        // 방법 2)
        PriorityQueue<Info> pq = new PriorityQueue<Info>((o1, o2) -> o1.dist - o2.dist);

        // 시작점에 대한 정보를 기록에 추가하고, 거리 배열(dist)에 갱신해준다.
        pq.add(new Info(start, 0));
        dist[start] = 0;
    }

2. D가 비었는지 확인 후 가장 작은 d를 가진 (v, d) 추출하고, 가치가 있는지 판단

        // D가 빌 때까지 반복
        while (!pq.isEmpty()) {
            Info info = pq.poll();
            
            // 꺼낸 정보가 최신 정보와 다르면, 가치가 없으므로 제외
            if (dist[info.idx] < info.dist) continue;
        }

3. (v, d)를 통해 새로운 정보를 D에 추가

        // 연결된 모든 간선들을 통해 다른 정점들에 대한 정보 갱신
        for (Edge e : edges[info.idx]) {
            // e.to까지 갈 수 있는 더 짧은 거리가 아니면 제외
            if (dist[info.idx] + e.weight >= dist[e.to]) continue;

            // 최단 거리를 갱신하고 D에 추가
            dist[e.to] = dist[info.idx] + e.weight;
            pq.add(new Info(e.to, dist[e.to]));
        }

---

출처

• https://github.com/rhs0266/FastCampus/blob/main/%EA%B0%95%EC%9D%98%20%EC%9E%90%EB%A3%8C/02-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/14-%EC%B5%9C%EB%8B%A8%EA%B1%B0%EB%A6%AC/02-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-14-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC.pdf