최단 경로를 찾는 데 자주 사용되는 알고리즘은 여러 가지가 있다.
1. One-To-One 한 지점에서 다른 특정 지점까지의 최단경로 구하기
2. One-To-All 한 지점에서 다른 모든 지점까지의 최단경로 구하기
3. All-To-All 모든 지점에서 모든 지점까지의 최단경로 구하기
문제의 조건마다 사용되는 알고리즘이 다르기때문에 적절히 선택해서 사용해야 한다.
그러려면 어떤 알고리즘이 있는지 알아야 할 것!
1. 다익스트라(Dijkstra) 알고리즘
목적
단일 시작점에서 다른 모든 노드까지의 최단 경로를 구하는 것
원하는 목적지가 나오면 종료할 수도 있음
그래프 유형
가중치가 있는 방향성 또는 무방향성 그래프 - 음수 가중치 허용 X
시간복잡도
O((V+E)⋅logV)
구현방식
1. 시작 노드의 거리를 0으로 설정하고, 다른 노드는 무한대로 초기화
2. 아직 처리되지 않은 노드 중 거리가 가장 짧은 노드를 선택
3. 선택된 노드를 기준으로 인접 노드의 거리 갱신
4. 모든 노드를 처리할 때까지 반복
특징
음수 가중치가 없을 경우 가장 빠르고 효율적
우선순위 큐(힙)를 사용하여 효율적으로 구현 가능
자세한정리
2. 벨만포드(Bellman-Ford) 알고리즘
목적
단일 시작점에서 다른 모든 노드까지의 최단 경로를 구하는 것
그래프 유형
가중치가 있는 방향성 그래프 - 음수 가중치 허용 O
시간복잡도
O(V⋅E)
구현방식
1. 시작 노드에서 모든 노드의 거리를 무한대로 초기화하고, 시작 노드의 거리를 0으로 설정
2. 모든 간선을 V - 1 번 반복하여 탐색
3. V - 1 번의 반복 이후에도 거리 갱신이 발생한다면, 음수 사이클이 존재한다고 판단.
https://great-park.tistory.com/134
특징
음수 가중치 처리 가능
음수 사이클이 존재할 경우 알 수 있음
자세한 정리
3. 플로이드-워셜(Floyd-Warshall) 알고리즘
목적
모든 정점 간의 최단 경로를 구하는 것
그래프 유형
가중치가 있는 방향성 그래프 - 음수 가중치 허용 O
시간복잡도
O(V^3)
구현방식
1. V x V 크기의 거리 행렬 d[i][j]를 초기화
ex) d[i][j]는 노드 i에서 j로 직접 연결된 간선의 가중치 (없으면 무한대, 자기 자신은 0)
2. 중간 노드를 하나씩 추가하면서 최단경로를 갱신
ex) d[i][j] = min(d[i][j], d[i][k]+d[k][j])
3. 위 과정을 모든 노드 쌍에 대해 반복
특징
모든 노드 간의 최단 경로를 동시에 계산 가능
음수 가중치 간선은 허용되지만, 음수 사이클이 있을 경우 잘못된 결과가 나올수도 있음
동적 계획법 기반
자세한 정리
그럼 얘네를 어떤 문제에 써야할까??
1. 단일 시작점 문제 -> 다익스트라 or 벨만포드
음수 가중치가 없다? => 다익스트라
음수 가중치가 있다? => 벨만포드
2. 모든 쌍 최단 경로 문제: 플로이드-워셜
근데 플로이드-워셜의 시간 복잡도는 V^3... 정점이 많을수록 매우 느려짐
그래서 정점 수가 많으면 존슨 알고리즘도 있다
근데 음수 사이클이 있으면??
음수 사이클이 있는지 판별하는 문제인지 확인
판별만 하는 문제면 벨만포드로 확인해서 해결
그래도 최단거리 찾으라고 하면 음수 사이클이 포함된 경로 사용하지 않게 하는 처리하기