최단 경로 알고리즘
다익스트라 알고리즘(Dijkstra)
그리디
개념
•
한 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘
•
가중치가 음수가 아닌 그래프에서만 사용 가능
•
우선순위 큐를 이용해 가장 짧은 거리부터 방문
프로세스
1.
출발 노드 설정
2.
최단 거리 테이블 초기화
3.
방문하지 않은 노드 중에서 거리가 가장 짧은 노드를 선택(= 그리디)
4.
해당 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블 갱신
•
최단 거리 테이블을 직접 갱신하지 않고, 우선 순위 큐에 삽입하는 방식으로도 가능
•
매 단계에서 한 번 처리된 노드의 최단 거리는 고정 → 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해 가능
5.
3-4번을 반복
코드로 확인해볼까요?
import heapq
def dijkstra(start, graph, n):
distance = [float('inf') * (n + 1)] # 모든 노드의 최단거리 값을 무한대로 초기화
distance[start] = 0
pq = [(0, start)]
while pq:
dist, now = heapq.heappop(pq)
# 이미 처리된 더 짧은 경로가 있다면 건너뛰기
if distance[now] < dist:
continue
# 현재 노드의 인접 노드 확인
for neighbor, weight in graph[now]:
# 현재 노드를 거쳐 인접 노드로 가는 비용 계산
cost = dist + weight
# 더 짧은 경로라면, 최단거리를 갱신하고 큐에 추가해 다음에 처리
if cost < distance[neighbor]:
distance[neighbor] = cost
heapq.heappush(pq, (cost, neighbor))
return distance
# 노드 수, 간선 수
n, m = 6, 11
graph = [[] for _ in range(n + 1)]
edges = [
(1, 2, 2), (1, 3, 5), (1, 4, 1),
(2, 3, 3), (2, 4, 2),
(3, 2, 3), (3, 6, 5),
(4, 3, 3), (4, 5, 1),
(5, 3, 1), (5, 6, 2)
]
for a, b, c in edges:
graph[a].append((b, c))
print(dijkstra(1, graph, n)) # 1번 노드에서 각 노드까지의 최단거리
Python
복사
플로이드 워셜 알고리즘(Floyd-Warshall)
다이나믹 프로그래밍(DP)
개념
•
모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘
•
다익스트라와 달리 시작점이 고정되어 있지 않음
•
음수 간선 허용(단, 음수 사이클은 허용 X)
•
동적 계획법(DP)를 활용한 알고리즘
프로세스
1.
2차원 테이블에 최단 거리 정보를 저장
2.
각 단계마다 특정한 노드 K를 거쳐 가는 경우를 확인
•
A → B로 가는 최단 거리보다 A → K → B로 가는 거리가 더 짧은지 검사
•
점화식 : D[A][B] = min(D[A][B], D[A][K] + D[K][B])
코드로 확인해볼까요?
def floyd_warshall(n, edges):
distance = [[float('inf')] * n for _ in range(n)] # 모든 노드의 최단 거리 값을 무한대로 초기화
for i in range(n):
distance[i][i] = 0
for a,b,cost in edges:
distance[a][b] = cost
for k in range(n):
for i in range(n):
for j in range(n):
distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
return distance
n = 4 # 노드 수
edges = [
(0, 1, 5),
(0, 3, 10),
(1, 2, 3),
(2, 3, 1),
]
print(floyd_warshall(n, edges))
Python
복사
비교 정리
항목 | 다익스트라 | 플로이드-워셜 |
최단거리 범위 | 한 정점 → 전체 | 모든 정점 → 모든 정점 |
시간복잡도 | O(E * logV) | O(V^3) |
음수 간선 허용 범위 |  |  |
사용 자료구조 | 우선순위 큐 | 2차원 배열 |