분류

  • 최단 경로 알고리즘
  • 동적 계획법

알고리즘 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def floyd_warshall(A, n):
    '''
    A: 인접 행렬
    n: 정점의 개수
    '''
    D = []
    for i in range(n):
        D.append([])
        for j in range(n):
            D[i].append(A[i][j])

    for k in range(n):
        for a in range(n):
            for b in range(n):
                D[a][b] = min(D[a][b], D[a][k] + D[k][b])

    return D

설명

다익스트라 알고리즘과 함께 대표적인 최단 경로 알고리즘 중 하나이다.

모든 지점에서 최단 거리를 구할 수 있으며, 다익스트라 알고리즘보다 구현이 더 간단하다.

$O(V^3)$의 복잡도를 가지기 때문에 빠른 알고리즘은 아니다.

$$
D_{ab} = min(D_{ab}, D_{ak} + D_{kb})
$$

간단한 점화식을 외우고 있으면 실전에서 사용하기 좋다.

복잡도

$O(V^3)$