플로이드 와샬 알고리즘(Floyd-Warshall Algorithm)

플로이드 와샬 알고리즘이란?  

양 또는 음의 에지 가중치를 갖는 방향 가중 그래프에서 각각의 정점에서 정점까지의

 모든 최단 경로를 찾는 알고리즘이다.

 

---

다시, 이전의 다익스트라와 벨만포드의 경우 두 정점간의 최소 거리를 계산했다면 플로이드와샬 알고리즘은 모든 정점간의 최소 거리를 알아내는 알고리즘이다. 

 

다른 알고리즘들과 달리 구현이 매우 쉽다.

3중 for 문을 사용하며 O(V^3)의 시간 복잡도를 갖고 있다. 

그럼 작동방식은 어떠할까? 아래 그림을 잠깐 보도록 하자 

 

인접행렬로 행과열의 값 arr[a][b] 는 a에서 b로 가는 비용이다.

일단 주어진 가중치를 인접행렬에 갱신해준다. 

 

 

그렇다면 이젠 가정이 필요하다. 

a에서 c까지 가는 경로가 있다고 보자,

그런데 a->b->c로 가는 경로가 더 싸다면??

arr[a][b] = arr[a][b] + arr[b][c] 가 된다.

 

그렇기에 3중 for문을 통해 위와 같은  arr[a][b] = arr[a][b] + arr[b][c] 계산을 반복해주는 것이다. 

결과적으로 위에 행렬이 완성된다. 

 

 

코드는 아래와 같다.

코드를 보고 다시금 이해해보자. 

 

---

11403번: 경로 찾기

import sys
input = sys.stdin.readline

N = int(input().rstrip())
matrix = [list(map(int, input().rstrip().split())) for _ in range(N)]

for k in range(0, N):   # 경유지를 위해 
    for i in range(0, N):   
        for j in range(0, N):
            if matrix[i][k]==1 and matrix[k][j]==1:
                matrix[i][j] = 1


for m in matrix:
    print(*m)

 

그림참고) https://github.com/epomp447/Floyd-Warshall-Algorithm-Java-