플로이드 와샬 알고리즘

언제 써야 하는가? )

'모든 정점'에서 '모든 정점'으로의 최단 경로를 구하고 싶다면 플로이드 와샬 알고리즘을 사용해야 한다

 

핵심 아이디어 )

'거쳐가는 정점'을 기준으로 최단거리를 구하는 것.

 

각각의 정점이 다른 정점으로 가는 비용을 이차원 배열의 형태로 저장한다.

 

저울 소스코드중...

 

graph = [[INF] * (n + 1) for _ in range(n + 1)]

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 = map(int, input().split())
    graph[a][b] = 1

a -> b로 갈 수 있으면 1로 해주고 가지 못하는 방향이라면 INF로 디폴트값을 해준다.

0 값은 같은 값에서 같은 값으로 이동할 수 없으니까

이렇게 2차원 배열로 정점에서 정점으로 가는 최소 비용을 기록해 둔다.

반복적으로 갱신해 최종적으로 모든 최소 비용을 구할 것이다.

 

최소 비용을 구하기 위한 비교는

a에서 b로 가는 최소 비용 VS a에서 노드1로 가는 비용 + 노드 1에서 b로 가는 비용을 비교한다