플로이드-워셜

플로이드-워셜

• 다익스트라: 출발점을 정했을 때 다른 노드에 이르는 최단거리.
• 플로이드-워셜: 모든 지점에서 다른 모든 지점까지 최단거리.
  • 시간복잡도 O(N^3)
• 핵심은 점화식!
  • D_{ab} = min(D_{ab}, D_{ak} + D_{kb})
  • a에서 b로 가는 거리 = a에서 b로 바로 가는 경우와 a에서 k를 거쳐 b를 가는 비용의 최솟값
• 각 노드별로 해당 노드를 거쳐가는 경우를 고려해서 최단 경로를 갱신하면 끝!
• 예를 들어 1번 노드를 거쳐가는 경로는
• D23 = min(D23, D21 + D13)
• D24 = mIn(D24, D21 + D14)
• D32 = min(D32, D31 + D12)
  
• D34 = min(D32, D31 + D14
• D42 = min(D42, D41 + D12)
• D43 = min(D43, D41 + D13)

• 맨 처음에 자기 자신까지의 거리는 0으로 설정하고 연결되어 있지 않은 노드에 대해선 INF로 설정하자.

# 노드 갯수
n = 4

# 연결된 노드(x[0], x[1])와 거리(x[2])
distances = [
    [1, 2, 4],
    [1, 4, 5],
    [2, 1, 3],
    [2, 3, 1],
    [3, 1, 6],
    [3, 4, 2],
    [4, 3, 7]
]
# 그래프 inf로 초기화
graph = [[float('inf')] * (n + 1) for _ in range(n + 1)]

# 자기 자신과의 거리는 0으로 초기화
for i in range(1, n + 1):
    graph[i][i] = 0

# 각 노드 사이의 거리 저장
for x, y, d in distances:
    graph[x][y] = d

# 플로이드 워셜 알고리즘

for i in range(1, n + 1):
    for x in range(1, n + 1):
        for y in range(1, n + 1):
            graph[x][y] = min(graph[x][y], graph[x][i] + graph[i][y])

print(graph)