[알고리즘] 플로이드-워셜 알고리즘

플로이드-워셜(Floyd-Warshall) 알고리즘

그래프의 모든 노드 간 최단 거리를 구하는 알고리즘이다.

시간 복잡도는 $O(n^3)$이므로 모든 최단 경로가 필요하지만 노드의 수가 적을 때 사용할 수 있다.

 

아이디어

한 노드(k)가 다른 두 노드(a, b)의 중간지점이라 생각한다면,

a에서 b로 가는 경로는 $a-k-b$ 이다. (k가 a혹은 b라면 경로는 a-b가 된다.)

$a-k-b$를 모두 조사한다면 a-b간 최단 경로를 알 수 있다.

 

아래와 같은 그래프를 가정하면

2를 중간 노드로 둘 경우, 2-2-3, 2-2-5, 3-2-5의 세 가지 경로의 값을 알 수 있다.

이 값들 중에서 3-2-5의 경우 3-5로 가는 경로보다 값이 작으므로 업데이트 해준다.

 

코드

for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
             if board[a][b] > board[a][k]+board[k][b]:
             	board[a][j] = board[a][k]+board[k][b]

 

 

관련 문제

 

코딩테스트 연습 - 합승 택시 요금