최적 경로 찾기 알고리즘 BFS, DFS, Dijkstra, A* ,Bellman-Ford

용어 정리

정점 Vertex : 그래프에서 하나의 노드를 의미. v1,v2와 같은 방식으로 표현하며 |V|는 정점의 갯수다
단순히 a,b,c...로 표현하기도 한다
간선 Edge : 정점과 정점을 연결하는 선. 방향성과 가중치가 있을 수 있다. E = {(v1,v2), (v2,v3), (v3,v1)}같은 형태로 나타낸다.
방향성이 있는 유향그래프에서는 v1→v2 와 같이 나타낸다
가중치 Weight : 그래프의 간선에 할당된 값. 두 정점간의 관계, 연결 비용, 거리, 시간등을 나타낸다
무가중치 그래프 : A-B-C
가중치 그래프 : A-(1)-B-(-3)-C

BFS (너비 우선 탐색, Breadth First Search)

시작 노드에서 가까운 노드부터 차례대로 탐색하는 알고리즘
큐로 구현한다. 가중치가 없는 최단 경로 탐색에 유용하다

작동 원리

1. 초기화
   a. 모든 노드의 방문을 거짓으로 표시
   b. 빈 Que 생성
   c. 방문 노드를 기록할 Set 생성
2. 시작 노드 처리
   a. 시작 노드를 참으로 표시
   b. 시작 노드를 que와 Set에 넣기
3. 탐색 과정 : que가 빌때까지 반복
   a. que에서 노드를 빼서 현재 노드로 설정
   b. 현재 노드의 인접 노드가 미방문이면
   Ⅰ. 노드를 참으로 표시
   Ⅱ. 노드를 que와 Set에 추가

시간 복잡도

$O(V + E)$

DFS (깊이 우선 탐색, Depth First Search)

한 경로를 끝까지 탐색한 후 백트래킹 하여 다른 경로를 탐색한다
스택 또는 재귀로 구현된다. 미로 탐색과 같은 문제에 유용하다

작동 원리

0. a. 각 노드별로 인접 노드를 배열로 저장한다
   b. 각 노드별로 방문 여부를 boolean으로 저장하는 배열을 생성한다
1. 초기화
   a. 모든 노드의 방문 여부를 거짓으로 표시
   b. 빈 스택 생성
2. 시작 노드 처리
   a. 시작 노드를 참으로 표시하고 스택에 푸시
3. 탐색 : 스택이 빌때까지 반복
   a. 스택의 top 노드를 현재 노드로 설정
   b. 현재 인접 노드 중 미방문 노드가 있는 경우
   Ⅰ. 참으로 변경
   Ⅱ. 해당 노드를 스택에 푸시
   Ⅲ. 모든 인접 노드가 참인 경우 현재 노드를 pop (백트래킹)

시간 복잡도

$O(V + E)$

Dijkstra (다익스트라)

가중치가 있는 그래프에서 한 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘
Heap(우선 순위 큐)로 구현 가능. 가중치가 음수인 경우에는 무한 루프에 빠질 수 있다
예) 여행을 갈때 이동시간이 아니라 비용을 기준으로 산정을 하면 여행지에서 취직해서 일한뒤 돈을 버는게 최소비용이 될 것이다

작동 원리

1. 테이블 : 첫 노드의 값을 0, 나머지 노드의 값을 무한(∞, INF(Infinity)으로 둔다
   힙 (0,v1) 쌍을 삽입
2. 힙 : 우선 순위가 가장 높은 힙을 추출 = 최단 경로가 확정된 노드
   테이블 : 추출된 노드의 값이 테이블의 값 이상이면 통과, 미만이면 이하 실행
   힙에서 추출한 노드에게 인접한 노드들에서,추출한 정점의 값 + 간선의 가중치이 기존의 값보다 작다면 갱신한다
   힙 : 갱신이 되었다면 (갱신값, 갱신노드)를 삽입
3. 2.번의 과정을 힙이 비는 순간까지 첫 노드부터 먼 노드까지 순서대로 반복한다

시간 복잡도

$O(E * logV)$

A*

최단 경로를 찾는 알고리즘, 휴리스틱 함수 (Heuristic Function)을 사용하여 총 예상 비용을 추정한다. 휴리스틱의 값이 (h(n) = 0)인 경우에 다익스트라 알고리즘과 동일해진다

작동 원리

1. 초기화
   a. 시작/목표 노드 설정
   b. 열린 목록/닫힌 목록 생성
   c. 시작 노드를 열린 목록에 추가
2. 평가 함수 설정
   f(n) = g(n) + h(n)
g(n) : 시작 노드에서 현재 노드까지의 실제 비용
   h(n) : 현재 노드에서 목표 노드까지의 추정 비용 (휴리스틱)
3. 탐색 과정 : 열린 목록이 빌때까지 반복
   a. 열린 목록에서 f(n)이 가장 작은 노드를 현재 노드로 선택
   b. 현재 노드가 목표 노드라면 탐색 종료
   c. 현재 노드를 닫힌 목록으로 이동
   d. 인접 노드들에 대해 이하 실행
   Ⅰ. 이동 불가 또는 닫힌 목록에 있으면 무시
   Ⅱ. 열린 목록에 이미 있다면, 새로운 경로의 g(n)이 기존 경로보다 작은 경우에만 f(n), g(n), 부모 노드를 갱신
   Ⅲ. 열린 목록에 있다면 더 나은 경로인지 확인하고 갱신
4. 경로 재구성 : 목표 노드에 도달했다면 부모 노드를 역추적하여 최단 경로 구성
5. 목표 노드에 도달했거나 열린 목록이 비어 있으면 알고리즘 종료

시간 복잡도

$O ( b * d )$
b : 분기 계수
d : 최단 경로의 깊이

다익스트라와 A*는 항상 같은 결과를 내는가?

주어진 조건이 작고 단순하다면 같은 결과를 내지만 크고 복잡하다면 휴리스틱에 따라서 편향된 탐사를 하는 A*가 다른 값을 내놓을 수 있다

Bellman-Ford (벨만 포드)

한 정점과 다른 모든 정점까지의 최단거리를 V-1회 탐색한다. 음수여도 제대로 작동한다

작동 원리

1. 테이블 초기화
   a. 시작 노드의 값을 0으로 초기화
   b. 그 외 모든 노드의 값을 ∞로 초기화
2. 시작 노드(u)와 인접한 노드(v)에 대해서 아래를 수행, w는 가중치(Weight)
   value(U) + W < value(V) 일시 갱신
   위의 과정을 모든 간선을 대상으로 실행 (이때 간선의 순서는 중요하지 않다)
3. 2의 과정을 V-1회 반복
4. 1회 더 반복해서 값에 갱신이 없다면 V-1회 반복한 테이블 반환
   값에 변화가 있다면 음수 사이클이 존재하여 최적 경로를 찾을 수 없음을 반환

시간복잡도

$O(V * E)$