✅

다익스트라, 플로이드 워셜

최단 경로 알고리즘

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

그리디

개념

•

한 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘

•

가중치가 음수가 아닌 그래프에서만 사용 가능

•

우선순위 큐를 이용해 가장 짧은 거리부터 방문

프로세스

출발 노드 설정

최단 거리 테이블 초기화

방문하지 않은 노드 중에서 거리가 가장 짧은 노드를 선택(= 그리디)

해당 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블 갱신

•

최단 거리 테이블을 직접 갱신하지 않고, 우선 순위 큐에 삽입하는 방식으로도 가능

•

매 단계에서 한 번 처리된 노드의 최단 거리는 고정 → 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해 가능

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)를 활용한 알고리즘

프로세스

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차원 배열