1. 최단 경로 알고리즘
최단 경로 알고리즘은 그래프(Graph)안에서 두 정점 사이를 이동할 때 가장 짧은 경로를 찾는 것을 의미한다.
대표적인 최단 경로 알고리즘으로는 다익스트라(Dijkstra), 벨만-포드(Bellman-Ford), 플로이드-워셜(Floyd-Warshall) 알고리즘 등이 존재한다.
2. 다익스트라 알고리즘
2.1 다익스트라 알고리즘이란?
다익스트라 알고리즘은 하나의 시작 정점으로부터 시작해 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.
최단 경로 문제를 해결한다는 것은 그래프 내부의 간선(Edge)들을 탐색하면서, 한 정점에서 다른 정점으로 이동할 때 간선들의 가중치 합이 가장 작은 경로를 찾는 것을 의미한다.
이 때, 경로를 구성하는 간선들의 가중치 합을 경로 비용(Path Cost / Path Weight)이라 한다.
※ 가중치란?
가중치란 간선(Edge)에 부여된 값으로 정점과 정점 사이를 이동하는데 드는 비용, 거리, 시간 등을 의미한다.
최단 경로를 찾는 알고리즘 중 다익스트라 알고리즘은 간선의 모든 가중치들이 0 이상 일 때 사용할 수 있는 알고리즘이다.
예를 들어 도로의 거리, 이동 시간, 교통비 등은 일반적으로 음수가 될 수 없기 때문에 다익스트라 알고리즘은 실생활의 문제를 해결하는 데 적합하다.
반면, 간선에 음수 가중치가 존재하는 경우에는 올바른 최단 경로를 찾지 못할 수 있기 때문에 다익스트라 알고리즘을 사용할 수 없다.
2.2 다익스트라 알고리즘의 동작 방식
아래의 예시를 보면서 다익스트라 알고리즘의 동작방식을 이해해보자.
1. 시작 정점의 거리를 0으로 설정하고, 나머지 정점들의 거리는 무한대(∞)로 초기화한다.
2. 아직 방문하지 않은 정점들 중에서 현재 최단 거리가 가장 작은 정점을 선택한다
3. 선택한 정점을 거쳐 갈 수 있는 다른 정점들의 거리를 계산한다.
4. 새로 계산한 거리가 기존 거리보다 더 작으면 최단 거리를 갱신한다.
5. 모든 정점을 방문할 때까지 이 과정을 반복한다.
3. 너비 우선 탐색 (BFS) vs 다익스트라(Dijkstra)
다익스트라 알고리즘과 BFS는 모두 그래프 탐색 알고리즘이지만, 다익스트라는 가중치를 고려하여 최단 경로를 찾는 반면, BFS는 가중치를 고려하지 않고 시작 정점부터 레벨 순으로 차례대로 탐색하는 방식이다.
즉 두 알고리즘은 같은 목적의 알고리즘은 아니다. 따라서 활용하는 자료구조에서도 차이를 보인다.
| 비교 | 다익스트라 | 너비 우선 탐색 |
| 사용환경 | 가중치 있는 그래프에서 주로 사용 | 가중치가 없는 그래프에서 사용 |
| 동작 방식 | 현재까지 확인한 경로 중 가장 비용이 적은 정점을 선택해 탐색 |
시작 정점으로부터 가까운 정점부터 레벨(Level) 순서대로 탐색 |
| 활용하는 자료구조 | 우선순위 큐(Priority Queue) | 큐(Queue) |
| 시간 복잡도 | O((V + E)logV) | O(V+E) |
4. 우선순위 큐(Priority Queue)와 힙(Heap)이 왜 사용될까?
4.1 우선순위 큐
우선순위 큐는 언제나 현재까지 계산된 거리 중 가장 작은 값을 가진 정점을 먼저 선택하는 자료구조이다.
👉 다익스트라 알고리즘이 우선순위 큐를 사용하면 최단 경로가 될 가능성이 높은 정점부터 탐색할 수 있어서 불필요하게 더 긴 경로를 탐색하는 횟수를 줄일 수 있다.
다익스트라 알고리즘은 매 단계마다 가장 짧은 거리를 가진 정점을 먼저 선택한다. 이렇게 선택된 정점은 해당 정점까지의 최단 거리가 확정된 상태이다. 따라서 인접한 정점들의 거리 또한 갱신하게 된다.
만약 같은 정점이 이후에 우선순위 큐에 다시 들어오더라도, 이미 더 짧은 거리로 처리된 적이 있다면, 다시 탐색할 필요가 없는 것이다.
👉 해당 정점을 거쳐 갈 수 있는 더 짧은 경로는 이미 반영되었기 때문이다.
4.2 힙 (Heap)
힙은 우선순위 큐를 효율적으로 구현하기 위해 사용하는 자료구조이다.
최소힙(Min Heap)은 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같은 완전 이진 트리 형태를 띈다. 따라서 트리에서 가장 작은 값은 항상 루트 노드에 위치하게 된다.
👉 다익스트라 알고리즘에서는 현재까지 계산된 거리 중 가장 작은 값을 가진 정점을 반복적으로 선택해야 한다.
👉 힙을 사용하지 않으면, 매 단계마다 모든 정점을 순회하며 가장 작은 거리 값을 찾아야 하지만, 최소 힙을 사용하면 가장 작은 값을 가진 정점을 쉽게 찾아 불필요한 탐색을 줄일 수 있다.
5. 🕐 다익스트라 알고리즘의 시간복잡도
일반 배열 자료구조를 활용했을 때
보통 O(V²)의 시간 복잡도를 가진다.
다익스트라 알고리즘은 매 단계마다 방문하지 않은 정점 중 최단 거리가 가장 짧은 정점을 선택해야 한다.
이 때 일반 배열을 사용하면 이 정점을 찾기 위해 모든 정점을 순회하며 최소 거리를 직접 비교해야 한다.
따라서 정점의 개수가 V개라면 최단 거리를 가진 정점을 찾는 과정에 O(V)의 시간이 걸린다. 이 과정을 모든 정점에 대해 반복하게 되므로 전체 시가 복잡도는 O(V²)가 된다.
우선순위 큐(최소 힙)를 활용했을 때
보통 O((V + E) log V) 의 시간복잡도를 가진다.
우선순위 큐(최소 힙)를 사용하면 최단 거리가 가장 작은 정점을 빠르게 선택할 수 있다.
일반 배열처럼 모든 정점을 순회하며 최소값을 찾을 필요가 없으며, 힙의 루트 노드에 항상 가장 작은 거리 값이 위치하기 때문이다.
또한, 간선을 탐색하면서 최단 거리가 갱신될 경우 해당 정점을 우선순위 큐에 다시 삽입한다.
다익스트라 알고리즘은 모든 정점을 한 번씩 선택하고(V), 모든 간선을 한 번씩 확인(E)한다.
힙의 삽입과 삭제 연산의 시간복잡도는 O(logV)이므로 전체 시간복잡도는 O((V+E)logV)가 된다.
6. 다익스트라 알고리즘 구현해보기
6.1 그래프 그리기
lass WeightedGraph:
def __init__(self):
self.graph = {}
# 정점 추가
def add_vertex(self, vertex):
if vertex not in self.graph: # 그래프의 키로 vertex가 없으면 빈 리스트를 가진 키-값을 만드러준다
self.graph[vertex]= []
# 간선 추가
def add_edge(self, start, end, weight):
# start 정점이 있는 지 체크해보기
if start not in self.graph:
print('start 정점이 현재 그래프에 없습니다')
return
self.graph[start].append((end,weight))
# 그래프 출력
def print_graph(self):
for start in self.graph:
print(start,':',end=' [')
for vertex in self.graph[start]:
print(f'({vertex[0]}, {vertex[1]})', end=', ')
print(']')
print()
노드와 가중치 있는 간선들 추가 후, 그래프 구조 출력해보기
g = WeightedGraph()
g.add_vertex("A")
g.add_vertex("B")
g.add_vertex("C")
g.add_vertex("D")
g.add_vertex("E")
g.add_edge("A", "B", 4)
g.add_edge("A", "C", 2)
g.add_edge("B", "D", 5)
g.add_edge("C", "B", 1)
g.add_edge("C", "D", 8)
g.add_edge("D", "E", 3)
g.print_graph()
그래프 출력 실행 결과
한 번 이 결과를 그래프로 그려보면 아래와 같다.
6.2 일반 배열을 활용해 다익스트라 알고리즘 구현해보기
1️⃣ 시작 정점 ~ 모든 정점 최단 거리 구하는 list_dijkstra 함수
❶ 초기화
- distance_rec : 시작 정점에서 각 정점까지의 최단 거리를 저장할 딕셔녀리 (key:정점 , value:길이)
- visited : 방문여부를 저장하는 딕셔너리 (key : 정점, value: T/F)
- previous : 각 노드별 경로를 저장하는 딕셔너리 (key: 정점 , value : [지나온 정점들])
def list_dijkstra(self,start):
# ✅ 시작 정점에서 각 정점까지의 최단 거리를 저장할 공간
distance_rec = {}
for vertex in self.graph:
distance_rec[vertex] = INF # 모든 정점과의 거리 무한대로 설정
distance_rec[start] =0 # 시작정점: 자기 자신과의 거리 =0
visited= {} # ✅ 방문 여부 저장하기 : 각 정점을 이미 방문했는 지 확인하기 위해 방문 딕셔너리를 만든다
for vertex in self.graph:
visited[vertex] = False # 처음에는 전부 방문하지 않는 상태로 초기화한다.
# ✅ 경로 저장하기
previous = {}
for vertex in self.graph:
previous[vertex] = None ❷ 최소 거리 정점 찾기
초기화가 끝난 후, 방문하지 않은 정점들 중 가장 짧은 거리를 가진 정점을 선택해야 한다.
모든 정점을 순회하며 현재까지 계산된 거리 값을 직접 비교한다. 이 과정에서 가장 짧은 거리를 가진 정점이 선택되고, 해당 정점의 최단 거리는 확정된 것으로 간주한다.
# 아직 방문하지 않은 정점 중 거리가 가장 짧은 정점 찾기
for i in range(len(self.graph)): # 정점의 개수만큼 탐색을 반복한다
min_distance = INF # 최소 거리는 무한대로 초기화
current = None # 가장 가까운 정점 : None으로 일단 초기화함
for vertex in self.graph: # 모든 정점을 순회하면서
# 아직 방문하지 않았고, min_distance 보다 짧은 거리를 찾으면
if not visited[vertex] and distance_rec[vertex] < min_distance:
min_distance= distance_rec[vertex] # min_distance 갱신
current = vertex # current 갱신
❸ 최단 거리 확정 및 방문 처리
가장 짧은 거리를 가진 정점을 찾으면 해당 정점의 최단 거리를 확정한다.
if current is None: # 더 이상 선택할 수 있는 정점이 없으면
break # 알고리즘 종료
visited[current] = True # 가장 가까운 정점의 최단 거리 확정 -> 방문 처리함 ❹ 인접 정점 거리 갱신 + 경로 정보 저장
현재 정점과 연결된 모든 인접 정점들을 체크하며 최단 거리 정보를 갱신한다.
또, 거리 정보가 갱신될 경우, 해당 정점에 도착하기 직전의 정점을 previous 딕셔너리에 기록한다.
# current 정점과 연결된 인접 정점들의 거리를 갱신
for next_vertex , weight in self.graph[current]:
new_distance = distance_rec[current] + weight # 시작 ~ 현재까지 거리 +인접 정점과 현재 정점 간 거리
if new_distance < distance_rec[next_vertex]: # 새로운 거리가 기존 거리보다 작으면
distance_rec[next_vertex] = new_distance # distance_rec 수정
# 경로 추가
previous[next_vertex] = current ❺ 결과 반환
모든 정점에 대한 최단 거리 계산이 완료 후, 최단 거리 정보와 경로를 함께 반환한다.
return distance_rec , previous 실행해보기
# g.print_graph()
# A : [(B, 4), (C, 2), ]
# B : [(D, 5), ]
# C : [(B, 1), (D, 8), ]
# D : [(E, 3), ]
# E : []
result = g.list_dijkstra("A")
print("A에서 각 정점까지의 최단 거리:", result[0])
실행결과
2️⃣ 시작 지점 ~ 모든 정점 의 경로 출력하는 함수 get_all_paths
👉 list_dijkstra 함수로부터 얻은 previous 딕셔너리를 활용해 모든 경로를 출력하도록 구현하였다.
def get_all_paths(self, start):
distance_rec, previous = self.list_dijkstra(start)
all_paths = {}
for vertex in self.graph:
path = []
current = vertex
while current is not None:
path.append(current)
current = previous[current]
path.reverse()
all_paths[vertex] = path
# return all_paths
for path in all_paths:
print(path,end=": ")
for node in all_paths[path]:
print(node,end=' ')
print()
g.get_all_paths('A')실행 결과
7. Heapq를 활용해 구현해보기
앞의 배열 기반 다익스트라 알고리즘 방식은 방문하지 않은 정점 중 최단 거리를 가진 정점을 찾기 위해 모든 정점을 순회해야 했다.
반면, 최소 힙을 사용하면 가장 작은 거리 값을 가진 정점이 항상 루트 노드에 위치하므로, 최단 거리르 가진 정점을 빠르게 선택할 수 있다.
❶ 초기화 및 우선순위 큐(최소 힙) 생성 + 시작 정점을 힙에 삽입
👉 시작 정점의 거리는 0이므로 (거리, 정점) 형태로 우선순위 큐에 저장(push)한다.
힙 : 첫번째 원소인 거리값을 기준으로 자동 정렬되므로 가장 짧은 거리를 가진 정점이 우선적으로 선택된다.
import heapq
def heap_dijkstra(self,start):
# 초기화 과정은 리스를 활용한 방식과 과정 같음 but 방문 기록은 구현하지 않음
distance_rec ={}
previous= {}
for vertex in self.graph:
distance_rec[vertex] = INF
previous[vertex] = None
distance_rec[start] = 0
pq =[] # 앞으로 탐색할 정점들 저장할 우선순위 큐
heapq.heappush(pq,(0,start)) # start ~ start의 거리는 0
## heappush(힙, (거리, 시작 정점))❷ 최단 거리 정점 선택
👉 heappop() : 현재 가장 가까운 정점을 return
while pq : # pq가 빌 때까지
current_distance ,current = heapq.heappop(pq) # 가장 가까운 정점 자동으로 꺼내기 ❸ 이미 처리된 경로는 무시 및 인접 정점 거리 갱신
list를 활용한 방식과 같다
👉 다만, 더 짧은 거리를 발견한 경우 해당 정점을 다시 힙에 push한다.
if current_distance > distance_rec[current]: # 이미 더 좋은 경로 나오면
continue # 무시
for next_vertex, weight in self.graph[current]: # 현재 노드와 인접한 노드들에 대해 조사
new_distance = weight + current_distance # 시작 노드 ~ 다음 노드 의 새로운 거리를 구하기
if new_distance < distance_rec[next_vertex]: # new_distance가 기존에 있었던 거리보다 작으면 갱신하기
distance_rec[next_vertex] = new_distance
previous[next_vertex] =current
heapq.heappush(pq,(new_distance, next_vertex)) # 더 짧은 거리를 발견했으므로 해당 (거리,정점)을 hp에 추가❹ 모든 반복을 마무리하고 distance_rec 과 previous를 return
return distance_rec, previous실행
print('A에서 각 정점까지의 최단 거리:',g.heap_dijkstra('A')[0])실행결과
8. 성능 비교
성능 비교 함수
import time
import random
def compare_time(graph, start):
start_time = time.perf_counter()
list_distance, list_previous = graph.list_dijkstra(start)
list_time = time.perf_counter() - start_time
start_time = time.perf_counter()
heap_distance, heap_previous = graph.heap_dijkstra(start)
heap_time = time.perf_counter() - start_time
print(f"리스트 버전 실행 시간 : {list_time:.8f}초")
print(f"heapq 버전 실행 시간 : {heap_time:.8f}초")
print("-" * 40)
if heap_time > 0:
print(f"heapq 버전이 약 {list_time / heap_time:.2f}배 빠릅니다.")
랜덤 그래프 그리는 함수(정점 개수, 간선 개수 지정)
def make_random_graph(vertex_count, edge_count):
g = WeightedGraph()
for i in range(vertex_count):
g.add_vertex(str(i))
for _ in range(edge_count):
start = str(random.randint(0, vertex_count - 1))
end = str(random.randint(0, vertex_count - 1))
weight = random.randint(1, 20)
if start != end:
g.add_edge(start, end, weight)
return g
실행
g2=make_random_graph(1000,5000)
compare_time(g2,'0')
실행결과
'python' 카테고리의 다른 글
| 그리디 알고리즘(Greedy Algorithm) (0) | 2026.06.22 |
|---|---|
| 탐색 알고리즘(Search Algorithm) (0) | 2026.06.16 |
| 정렬 알고리즘 - ③ 병합 정렬 (0) | 2026.06.12 |
| 정렬 알고리즘 ② - 퀵 정렬 (0) | 2026.06.12 |
| 재귀함수(Recursive Function) (0) | 2026.06.11 |