[알고리즘] 패스트캠퍼스 챌린지 28일차

[알고리즘] 패스트캠퍼스 챌린지 28일차

최단 경로 문제

최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제임

가중치 그래프 (Weighted Graph) 에서 간선 (Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적

최단 경로 문제 종류

단일 출발 및 단일 도착 (single-source and single-destination shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착 하는 가장 짧은 경로를 찾는 문제 단일 출발 (single-source shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제 따지고 보면 굉장히 헷깔릴 수 있으므로 명확히 하자면, 예를 들어 A, B, C, D 라는 노드를 가진 그래프에서 특정 노드를 A 라고 한다면, A 외 모든 노드인 B, C, D 각 노드와 A 간에 (즉, A - B, A - C, A - D) 각각 가장 짧은 경로를 찾는 문제를 의미함 전체 쌍(all-pair) 최단 경로: 그래프 내의 모든 노드 쌍 (u, v) 에 대한 최단 경로를 찾는 문제

이 중에 2번 유형에 해당하는 다익스트라 알고리즘에 대해 공부한다.

다익스트라 알고리즘

하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리 를 구하는 문제

를 구하는 문제 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법

첫 정점을 기준으로 각 정점까지의 거리를 저장할 배열을 만든다. 본인 - 본인 : 거리 = 0 본인 - 나머지 : 거리를 알 수 없으므로 무한대(inf)로 저장

=> 우선순위 큐(Queue)에 (첫 정점, 거리 0)을 넣는다. 우선순위 큐에서 노드를 꺼낸다. [1st] 첫 정점밖에 없으므로 첫 정점이 꺼내진다. 첫 정점에 인접한 노드들 각각에 대해 각 노드로 가는 거리와 현재 배열에 저장되어 있는 그 거리를 비교하고, 배열에 저장되어 있는 값보다 실제 거리가 더 짧으면 배열에 저장된 거리 정보를 업데이트한다. 업데이트 된 경우 우선순위 큐에 넣는다. 우선순위 큐에서 꺼낼 노드가 없을 때까지 위의 2번 과정을 반복한다.

어렵다..!

강의 돌리면서 설명 두번 들었다.

실제 예제 보면서 다시 이해해보기..

학습 예제

그래프: 방향그래프, 가중치 그래프

1. 첫 정점을 기준으로 각 정점까지의 거리를 저장할 배열을 만든다.

2. 우선순위 큐에서 노드를 꺼내고 배열에 저장된 거리보다 실제 거리가 짧으면 업데이트하고 업데이트 한 노드를 우선순위 큐에 넣는다.

3. 우선순위 큐에서 첫번째 노드를 꺼낸다. (C, 1)

위 표에서 보듯이 1단계까지의 A - B 최단 거리는 8 인 상황임 A - C 까지의 거리는 1, C 에 인접한 B, D에서 C - B는 5, 즉 A - C - B 는 1 + 5 = 6 이므로, A - B 최단 거리 8보다 더 작은 거리를 발견, 이를 배열에 업데이트 배열에 업데이트했으므로 B, 6 (즉 A에서 B까지의 현재까지 발견한 최단 거리) 값이 우선순위 큐에 넣어짐 C - D 의 거리는 2, 즉 A - C - D 는 1 + 2 = 3 이므로, A - D의 현재 최단 거리인 2 보다 긴 거리, 그래서 D 의 거리는 업데이트되지 않음

4. 우선순위 큐에서 노드를 꺼낸다. (D, 2)

5. 우선순위 큐에서 노드를 꺼낸다. (E, 5)

6. 노드 꺼낸다. (B, 6)

제의 방향 그래프에서 B 노드는 다른 노드로 가는 루트가 없음

F 노드는 A 노드로 가는 루트가 있으나, 현재 A - A 가 0 인 반면에 A - F - A 는 6 + 5 = 11, 즉 더 긴 거리이므로 업데이트되지 않음

7. (F, 7) / (B, 8) 순서대로 꺼낸다.

A - F 로 가는 하나의 루트의 거리가 7 인 상황이나, 배열에서 이미 A - F 로 가는 현재의 최단 거리가 6인 루트의 값이 있는 상황이므로, 더 긴거리인 F, 7 루트 기반 인접 노드까지의 거리는 계산할 필요가 없음, 그래서 계산없이 스킵함 계산하더라도 A - F 거리가 6인 루트보다 무조건 더 긴거리가 나올 수 밖에 없음

B, 8 도 현재 A - B 거리가 6이므로, 인접 노드 거리 계산이 필요 없음.

우선순위 큐 사용 장점¶

지금까지 발견된 가장 짧은 거리의 노드에 대해서 먼저 계산

더 긴 거리로 계산된 루트에 대해서는 계산을 스킵할 수 있음

원리.. 원리만 해도 이해하는데 한참걸렸당..

강의 듣는 중 사진 찌긍ㅁ

https://bit.ly/37BpXiC

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

from http://tnqtnq.tistory.com/105 by ccl(A) rewrite - 2021-10-03 20:01:05