최단경로 알고리즘 - BFS, 다익스트라, 플로이드-워셜, 벨만-포드, A*

date

Jul 25, 2023

slug

algo-chleksrudfh

author

status

Public

category

💡 Algorithm

tags

그래프

summary

그래프에서 최단 경로를 찾기 위한 알고리즘은 1)간선의 가중치 여부, 2)간선 가중치의 음수 가능 여부에 따라 분류할 수 있다.

type

Post

thumbnail

최단 경로 알고리즘

• BFS

• 다익스트라

• 플로이드-워셜

• 벨만-포드, A*

BFS

• 완전탐색을 통한 최단 경로 알고리즘

• 가중치가 없거나, 모든 가중치가 동일한 그래프에서 최단 경로를 구할 경우 BFS가 가장 빠름

다익스트라(Dijkstra)

• 음의 간선을 포함할 수 없는 가중 그래프에서의 최단 경로 알고리즘

• 특정한 하나의 정점에서 다른 모든 정점으로 가는 단일 쌍, 단일 출발, 단일 도착 최단 경로

• dp를 활용
• 왜 dp인가? 최단거리는 여러 개의 최단 거리의 합으로 이루어져 있기 때문

• 힙(우선순위큐) 사용하여 O(E logV)

• 상세 과정

1. 출발 노드를 설정
2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택
4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신
5. 3~4번을 반복하여 최소 비용 배열 갱신

• 시간복잡도
• 단순 선형 탐색으로 최소 비용을 찾으면 O(N * N)
• 그래프 저장 배열을 힙 구조(우선순위 큐)를 활용하여 O(E * logV) 구현 가능
• 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 최대 E번 가능

• 특징
• 그리디 알고리즘: 매 상황에서 방문하지 않은 가장 비용이 적은 노드 선택
• 단계를 거치며 한 번 처리된 노드(이미 방문 처리된 노드)의 최단 거리는 고정되어 바뀌지 않음

벨만-포드(Bellman-Ford)

• 음의 싸이클이 없는 그래프에서의 한 정점에서 모든 정점으로 가는 최단 경로 알고리즘
• 음의 가중치를 가지는 간선도 가능(사이클만 불가능)
• 음의 사이클 존재 여부를 확인할 수 있음

• 특정한 하나의 정점에서 다른 모든 정점으로 가는 단일 쌍, 단일 출발, 단일 도착 최단 경로

• 다익스트라 알고리즘과의 차이점
• 음의 가중치를 갖는 간선이 존재할 때 최단 경로 갱신 가능
• 음의 사이클이 존재하는지 여부 확인 가능

• 상세과정

1. 출발 노드를 설정
2. 최단 거리 테이블을 초기화
3. 다음의 과정을 (V-1)번 반복
3-1. 모든 간선 E개를 하나씩 확인
3-2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
3-3. 만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번 과정을 마지막에 한 번 더 수행(V번째)하여 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것

• 시간복잡도
• V번 반복에 대하여 해당 정점과 연결된 E개의 간선을 탐색하므로 O(V*E)

플로이드-워셜(Floyd-Warshall)

• 음의 가중치를 포함할 수 있는 가중 그래프에서의 최단 경로 알고리즘

• 모든 정점에서 다른 모든 정점으로 가는 전체 쌍 최단 경로, 다수 출발, 단일 도착 최단 경로

• 다익스트라 알고리즘과의 차이점
• 다익스트라는 음의 가중치는 허용하지 않음 ↔ 플로이드 워셜은 음의 가중치도 허용
• 다익스트라 알고리즘은 가장 적은 비용의 정점을 하나씩 선택해야 했다면 ↔ 플로이드 워셜 알고리즘은 기본적으로 ‘거쳐가는 정점’을 기준으로 알고리즘을 수행

• dp를 활용

• 3중 for문

• 상세과정

1. 노드를 설정
2. 모든 구간마다 해당 노드를 거쳐가는 경우의 최소 비용 갱신
3. 모든 노드에 대해 2번 반복

• 시간복잡도
• 3중 for문을 사용하므로 O(N^3)

A*

• F = 출발 지점에서 목적지까지 총 cost 합

• G = 현재 노드에서 출발 지점까지의 총 cost

• H = Heuristic 휴리스틱, 현재 노드에서 목적지까지의 추정거리

• F = G + H

Summary