최단 경로 문제 - 플로이드 워셜(Floyd-Warshall) 알고리즘

플로이드 워셜

플로이드 워셜 알고리즘을 쓰는 문제의 경우, 노드의 개수가 500개 이하일 경우가 많다.
하지만 노드가 500개라고 해도 500 * 500 * 500 은 1억이 넘어가기 때문에 시간제한이 넉넉하지 않다면 시간초과에 걸릴 수도 있다.

1. 플로이드 워셜 알고리즘 개요

• 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다.
• 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다.
  • 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다.
• 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다.
• 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다.

2. 플로이드 워셜 알고리즘

• 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다.
  • a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다.
• 점화식은 다음과 같다.

 

3. 플로이드 워셜 알고리즘: 동작 과정 살펴보기

 

4. 플로이드 워셜 알고리즘 구현 (Python)

INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에게 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
	for b in range(1, n + 1):
		if a == b:
			graph[a][b] = 0

# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for _ in range(m):
	# A에서 B로 가는 비용은 C라고 설정
	a, b, c = map(int, input().split())
	graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n + 1):
	for a in range(1, n + 1):
		for b in range(1, n + 1):
			graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과를 출력
for a in range(1, n + 1):
	for b in range(1, n + 1):
		# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
		if graph[a][b] == INF:
			print("INFINITY", end=" ")
		# 도달할 수 있는 경우 거리를 출력
		else:
			print(graph[a][b], end=" ")
    print()

5. 플로이드 워셜 알고리즘 성능 분석

• 노드의 개수가 N개일 때 알고리즘 상으로 N번의 단계를 수행한다.
  • 각 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다.
• 따라서 플로디으 워셜 알고리즘의 총 시간 복잡도는 O(N^3)이다.

---

최단 경로 문제 (이코테 ch7. 최단 경로 알고리즘 예시)

1.  <문제> 전보: 문제 설명

2.  <문제> 전보: 문제 조건

 

3. <문제> 전보: 문제 해결 아이디어

 

4. <문제> 전보: 답안 예시(Python)

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수, 시작 노드를 입력받기
n, m, start = map(int, input().split())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
for _ in range(m):
	x, y, z = map(int, input().split())
	# X번 노드에서 Y번 노드로 가는 비용이 Z라는 의미
	graph[x].append((y, z))

def dijkstra(start):
	q = []
	# 시작 노드로 가기 위한 최단 거리는 0으로 설정하여, 큐에 삽입
	heapq.heappush(q, (0, start))
	distance[start] = 0
	while q:  # 큐가 비어있지 않다면
		# 가장 최단 거리가 짧은 노드에 대한 정보를 꺼내기
		dist, now = heapq.heappop(q)
		if distance[now] < dist:
			continue
		# 현재 노드와 연결된 다른 인접한 노드들을 확인
		for i in graph[now]:
			cost = dist + i[1]
			# 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
			if cost < distance[i[0]]:
				distance[i[0]] = cost
				heapq.heappush(q, (cost, i[0]))

# 다익스트라 알고리즘을 수행
dijkstra(start)

# 도달할 수 있는 노드의 개수
count = 0
# 도달할 수 있는 노드 중에서, 가장 멀리 있는 노드와의 최단 거리
max_distance = 0
for d in distance:
	# 도달할 수 있는 노드인 경우
	if d != INF:
		count += 1
		max_distance = max(max_distance, d)

# 시작 노드는 제외해야 하므로 count - 1을 출력
print(count - 1, max_distance)