TIL(12일차) 플로이드 워샬 알고리즘

플로이드 워샬

 

플로이드 워샬 알고리즘은 다이나믹 프로그래밍 기법을 사용한 그래프 최단거리 구하기 알고리즘중 하나이다.

 

참으로 동적 프로그래밍은 중복된 연산을 줄이는 방법을 의미한다.

 

어떠한 그래프가 있다고 하면 어떠한 노드를 거쳐가는 것을 포인트로 하여 구현화한 알고리즘이다.

 

인접행렬표를 생성하고 T(1)이라고 하면 1번 노드를 거쳐서 해당 위치로 최소 가중치를 표에 계속 갱신한다.

 

아래와 같은 그림이 있다고 해보자

플로이드 워샬 알고리즘

 

T(p) -> T(1)이 있다고 하면

 

1을 거쳐서 가는 방법 즉, 2번 노드에서 1번을 거쳐서 3번노드를 가는 최소치와 4번노드를 가는 최소치를 갱신한다.

 

T(2)도 2번 노드를 거쳐서 1번,3번,4번을 가는 최소치를 갱신한다.

 

위와 같은 작업을 반복하면 그림의 오른쪽 표처럼 갱신이 된다.

 

모든 노드를 다 검사하면 row번 노드에서 col노드 까지의 최소거리가 나타난다.

 

즉, 모든 경우의 최소비용 행렬이 만들어 진것.

 

플로이드 워샬을 사용하여 이행적 패쇄를 구하기도 가능하다.

 

슈도 코드는 그림의 나와 있는것과 같이 나온다.

 

vertex, edge = map(int, input().split())

def floyd_warshall():
    global vertex, arr
    for k in range(1, vertex+1):             # pass node
        for i in range(1, vertex+1):         # start point
            for j in range(1, vertex+1):     # end point
                if d[i][j] > d[i][k] + d[k][j]:       # update minimum distance 
                    d[i][j] = d[i][k], d[k][j]

이행적 패쇄

두 정점간의 길이가 1인 이상인 경로의 존재 여부를 파악하는 알고리즘으로

 

정점 v(i)로 부터  v(j)로의 경로가 존재하면 1 존재하지 않으면 0으로 표현한다.

---

 

직관적이고 간단한 설명을 유튜버 동빈나 님 께서 해주신다 ^ㅁ^

 

https://www.youtube.com/watch?v=9574GHxCbKc