최단경로 알고리즘 이란?

그래프에서 두 노드 간의 최단경로를 찾는 문제를 해결하는 알고리즘.
다양한 응용 분야에서 중요한 역할을 하며, 가장 많이 사용되는 알고리즘으로는 다익스트라 알고리즘, 벨만 - 포드 알고리즘, 플로이드 - 위셜 알고리즘 등이 있음

다익스트라 알고리즘 (Dijkstra`s Argorithm)

특징

비음수 가중치 그래프에서 단일 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘

작동원리

1. 출발 노드를 설정하고, 초기 거리를 0으로, 다른 모든 노드의 거리를 무한대로 설정
2. 현재 방문하지 않은 노드 중에서 가장 작은 거리를 가진 노드를 선택
3. 해당 노드를 거쳐 다른 노드로 가는 거리가 기존 거리보다 짧으면 업데이트
4. 모든 노드를 방문할 때까지 2번과 3번 과정을 반복

시간복잡도

우선순위 큐를 사용하면 O((V + E) log V). 여기서 V는 정점의 수, E는 간선의 수

벨만 - 포드 알고리즘(Bellman - Ford Algoruthm)

특징

-음수 가중치가 있는 그래프에서도 사용 가능하며, 단일 출발점에서 다른 모든 정점까지의 최단 경로를 찾음
-음수 사이클을 감지할 수 있음

작동원리

1. 출발 노드를 설정하고, 초기 거리를 0으로, 다른 모든 노드의 거리를 무한대로 설정
2. 모든 간선에 대해 최대 (v - 1)번 반복하여 각 간선을 완화(relax) 함. 즉, 간선 u - v 의 가중치 w 에 대해 dist[v] > dist[u] + w 이면 dist[v] 를 업데이트 함
3. 추가적으로 한번 더 반복하여 거리가 업데이트 된다면, 음수 사이클이 존재

시간복잡도

O(VE)

플로이드 - 워셜 알고리즘(Floyd - Warshall Algorithm)

특징

-모든 정점 쌍 간의 최단 경로를 찾는 알고리즘
-음수 가중치를 허용하지만, 음수 사이클이 존재하면 사용할 수 없음

작동원리

1. 각 정점 쌍 (i, j)에 대해 초기 경로 값을 설정
2. 중간 정점 k 를 통해 경로를 개선할 수 있으면 경로 값을 업데이트 함
3. 모든 정점에 대해 반복

시간복잡도

O(V^3)

요약

1. 다익스트라 알고리즘
   -사용 : 비음수 가중치 단일 출발 최단 경로
   -시간복잡도 : O((V + E) log V) (우선순위 큐 사용)
   -장점 : 빠르고 효율적
   -단점 : 음수 가중치 간선 허용 안 함

2. 벨만 -포드 알고리즘
   -사용 : 음수 가중치 허용 단일 출발 최단 경로
   -시간 복잡도 : O(VE
   -장점 : 음수 사이클 감지 가능
   -단점 : 다익스트라보다 느림

3. 플로이드 - 워셜 알고리즘
   -사용 : 모든 정점 쌍 간 최단 경로
   -시간 복잡도 : O(V^3)
   -장점 : 단순하고 구현 쉬움
   -단점 : 대규모 그래프에서는 비효율적