WEEK03 - TIL 플로이드 워셜

플로이드 워셜(Floyd-Warshall)이란?

-모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산

-플로이드 워설 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘 수행

→다만 매 단계마다 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾는 과정이 필요X

-플로이드 워셜은 2차원 테이블에 최단 거리 정보 저장

-다이나믹 프로그래밍 유형에 속한다.

 

노드의 개수가 적은 상태에서 효과적으로 사용하고, 노드의 개수와 간선이 많은 경우는 다익스트라를 더 많이 사용한다.

 

점화식 : 

각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인

→ a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사

 

 

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