최단 경로 알고리즘 - 다익스트라 개념과 사용 가능한 문제 유형 정리

다익스트라란?

다익스트라 알고리즘은 최단 경로를 찾는 알고리즘으로, 보통 가중치 그래프에서 출발점에서 다른 노드들까지의 최소 거리를 구하는 문제이다.

 

다익스트라 알고리즘을 사용할 수 있는 문제 유형

1. 단일 출발점에서 모든 도착점까지의 최단 경로를 구하는 문제

- (예) 가장 빠른 경로를 찾거나 최소 비용 목적지에 도달하는 경로를 찾는 문제

- (예) 주어진 도시에서 다른 모든 도시에 최소 비용으로 가는 경로를 구하라.

 

2. 가중치가 있는 그래프에서 최단 경로를 찾는 문제

- 그래프의 각 간선에 가중치가 있을 떄, 그 가중치에 따른 최단 경로를 계산

- 가중치는 거리, 시간, 비용 등일 수 있음.

- (예) 다양한 도로가 주어지고, 각 도로마다 비용이 다를 때, 주어진 출발점에서 목적지까지 가는 최소 비용 경로를 구하라

 

3. 양방향 그래프에서 최단 경로

 - (예) 각 도시가 도로로 연결된 그래프가 주어질 때, 한 도시에서 다른 도시까지의 최소 비용을 구하라

 

4. 그래프가 연결되어 있고, 간선에 음의 가중치가 없는 경우

- 양의 가중치만 있을 때만 가능

- 음의 가중치가 있다면, 벨만-포드 알고리즘 사용해야 함.

- (예) 비용이 양의 값인 간선만을 가진 네트워크에서 최소 비용을 구하라.

 

5. 우선순위 큐(Heap)을 사용한 경로 탐색이 필요한 경우

- 우선순위 큐(Priority Queue)를 활용해, 현재까지 발견된 최단 경로를 확장하면서 최소 비용을 가지는 경로를 우선적으로 처리하는 방식

 

다익스트라 알고리즘을 사용하면 안되는 문제 유형

1. 그래프에 음의 가중치가 있는 경우

- 벨만-포드 알고리즘을 사용해야 함.

 

2. 모든 쌍에 대한 최단 경로 문제

- 여러 출발지에서 여러 도착지까지의 최단 경로를 구하려면 플로이드-워셜 알고리즘 사용해야 함.

 

3. 그래프가 비연결된 경우

- 다익스트라는 연결된 그래프에서만 동작함

- 비연결 그래프면, 일부 노드로는 도달할 수 없다는 걸 고려하여 -1을 반환하는 방식으로 처리 가능.