플로이드 워셜 알고리즘

플로이드 워셜 알고리즘

플로이드 워셜 알고리즘Foyd-Warshall Algorithm은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 할 경우에 사용할 수 있는 알고리즘이다.

 

점화식

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

 

위 점화식을 보면 , 기본 아이디어가 dp = 기존 값, 중간에 뭔가 거쳐서 갱신된 값. 이 기본 아이디어 임을 알 수 있다.

 

진행 방식

1) 그래프의 간선에 따라 최단거리 테이블을 초기화 한다.

2) N번 노드를 거쳤을 때 위 점화식에 따라 최단거리 테이블의 갱신작업을 진행한다.

 

동작 예시

아래와 같은 그래프가 있을 때, 최단거리 테이블 또한 동일하게 초기화한다.

[ 0, 3, 8, INF ] [ INF, 0, 2, 5 ] [ INF, INF, 0, 1 ] [ INF, INF, INF, 0 ]

 

1) 노드 0을 거쳐 갱신: 갱신할 원소가 없음.

[0, 3, 5, 8] [INF, 0, 2, 5] [INF, INF, 0, 1] [INF, INF, INF, 0]

 

2) 노드 1을 거쳐서 갱신: 0 -> 1 - > 2 번 노드로 가는게 5로 갱신됨, 0 -> 1 -> 4 번 노드로 가는게 8로 갱신됨

[0, 3, 5, 6] [INF, 0, 2, 3] [INF, INF, 0, 1] [INF, INF, INF, 0]

 

3) 노드 2을 거쳐서 갱신: 0 -> 2 - > 4 번 노드로 가는게 6로 갱신됨, 1 -> 2 -> 4 번 노드로 가는게 3로 갱신됨

 

4) 노드 3을 거쳐 갱신: 갱신할 원소 없음

[0, 3, 5, 6] [INF, 0, 2, 3] [INF, INF, 0, 1] [INF, INF, INF, 0]

 

위의 갱신된 그래프를 따라서 0 -> 3노드로 가는 최소 비용은 6이다.

 

구현 코드

On^3의 복잡도로 구현 가능하다. A->B 까지 가는데에 C를 거친다...라는 아이디어 래서 아래와 같이 구현 할 수 있다.

INF = 10e9
graph = [
    [0, 4, INF, 6],
    [3, 0, 7, INF],
    [5, INF, 0, 4],
    [INF, INF ,2 ,0]
]

for i in range(4):
    s = i
    for j in range(4):
        m = j
        for k in range(4):
            e = k
            graph[s][m] = min(graph[s][m], graph[s][e] + graph[e][m])

print(graph[0][2])