[Python/코테] 플로이드-와샬 알고리즘 - 개념, 코드

경기 순위 비교 문제를 풀다가 알게 된 그래프 알고리즘.

다른 빈출 그래프 알고리즘에는 다익스트라, 벨만-포드 알고리즘이 있고 BFS, DFS도 그래프 알고리즘이다.

 

모든 정점에서 모든 정점으로 가는 경우(최단거리)를 파악하는 알고리즘이다. 이차원 배열을 사용하여 반복적으로 값을 갱신하며 모든 최소비용을 구한다. 

그래프 알고리즘으로 유명한 다익스트라 알고리즘은 일차원 배열을 사용하여 매번 가장 작은 비용을 가지는 노드를 중심으로 활용하고, 플로이드-와샬은 이차원 배열을 사용하여 모든 노드를 거친다는 차이가 있다.

a → b 경로의 값과, a → k → b 로 가는 경우의 값을 비교하여 최소값을 배열에 저장(갱신)한다.

 

 

---

예제

위와 같은 그래프가 있다. 각 정점이 다른 정점으로 가는 비용을 이차원 배열로 표현하면 아래와 같다.

이는 현재까지 계산된 최소 비용을 의미한다. 이제 반복을 통해 테이블을 갱신하여 최종적으로 모든 최소 비용을 구해야 한다. * 무한은, 곧바로 갈 수 있는 경우가 없을 때이다. (돌고 돌아가면 경우의 수가 무한이 될 수 있어서 그런 것 같다.)

1. 노드1을 거쳐가는 경우

X에서 Y로 가는 최소 비용 (VS) X에서 노드 1로 가는 비용 + 노드 1에서 Y로 가는 비용

위와 같은 방식으로 반복하면, 아래와 같이 배열 값이 갱신된다.

2. 노드2를 거치는 경우

갱신될 수 있는 부분은 노란 색을 칠한 칸들이다. 자기 자신으로 가는 경우와, 노드2가 출발 혹은 도착이어서 포함하는 경우는 제외한다.

노드1을 거칠 때와 마찬가지로 비교 후 최소 값을 갱신해준다.

과정을 반복한 뒤, 결과적으로 아래와 같은 배열이 만들어진다.

3. 결과

노드3과 노드4에 대해서도 해당 노드를 거쳐가는 값을 기준으로 최소 값 찾기 수행하면, 결과적으로 아래와 같은 결과가 만들어진다.

---

코드 구현

n = 4
INF = 10000000

a = [[0, 5, INF, 8],
     [7, 0, 9, INF],
     [2, INF, 0, 4],
     [INF, INF, 3, 0]]


def floydWarshall():
    d = [[0] * n for _ in range(n)]
    # d = [row[:] for row in a] # a 배열 깊은 복사(원본 변경x)

    # 결과 그래프 초기화
    for i in range(n):
        for j in range(n):
            d[i][j] = a[i][j]

    # k = 거쳐가는 노드. 반복의 기준이 된다.
    for k in range(n):
        # i = 출발 노드
        for i in range(n):
            # j = 도착 노드
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]

    # 결과(최소 비용 배열) 출력
    for i in range(n):
        for j in range(n):
            if d[i][j] == INF:
                print("INF", end=" ")
            else:
                print(d[i][j], end=" ")
        print()


floydWarshall()

---

참고:

https://blog.naver.com/ndb796/221234427842

24. 플로이드 와샬(Floyd Warshall) 알고리즘

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

https://velog.io/@kimdukbae/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Floyd-Warshall-Algorithm

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

 

더 많은 그래프 유형 공부를 위해, 

https://velog.io/@boyeon_jeong/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%A2%85%EB%A5%98-%EB%B0%8F-%EA%B0%9C%EB%85%90

그래프 종류 및 개념 (알고리즘 문제 추천)