플로이드-워셜(Floyd-Warshall) 알고리즘 이론과 파이썬 구현

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

 

플로이드-워셜(Floyd-Warshall) 알고리즘은 모든 정점 사이의 최단 경로를 찾는 탐색 알고리즘입니다.

 

최단 경로는 길이 순으로 구해집니다.

 

플로이드 워셜 알고리즘의 과정입니다.

1. 하나의 정점에서 다른 정점으로 바로 갈 수 있으면 최소 비용을, 갈 수 없다면 INF로 배열에 값을 저장합니다.
2. 3중 for문을 통해 거쳐가는 정점을 설정한 후 해당 정점을 거쳐가서 비용이 줄어드는 경우에는 값을 바꿔줍니다.
3. 위의 과정을 반복해 모든 정점 사이의 최단 경로를 탐색합니다.

 

다음과 같은 단방향 그래프가 있으면 정점은 1, 2, 3, 4로 4개입니다.

간선은 1 → 2, 1 → 4, 2 → 1, 2 → 4, 3 → 1, 4 → 2, 4 → 3로 7개입니다.

 

플로이드-워셜 알고리즘은 각각의 점들을 거치는 경우를 생각해야 합니다.

 

Dist는 1부터 각 정점까지의 최단 경로를 담는 배열입니다.

 

 

시작점과 끝점이 1을 거치는 경우에 값이 기존 값보다 작은 경우 최단 경로를 Dist에 넣습니다.

3에서 2로 가는 방법이 INF였는데 3에서 1을 거쳐 2로 가는 방법이 5이기 때문에 Dist[3][2]는 5로 바꿔줍니다.
3에서 4로 가는 방법이 INF였는데 3에서 1을 거쳐 4로 가는 방법이 7이기 때문에 Dist[3][4]는 7로 바꿔줍니다.

 

4에서 1로 가는 방법이 INF였는데 4에서 2을 거쳐 4로 가는 방법이 4이기 때문에 Dist[4][1]는 4로 바꿔줍니다.

 

3을 거쳐가는 경우에는 변동이 없습니다.

 

1에서 3로 가는 방법이 INF였는데 1에서 4를 거쳐 3으로 가는 방법이 5이기 때문에 Dist[1][3]는 5로 바꿔줍니다.

2에서 3로 가는 방법이 INF였는데 2에서 4를 거쳐 3으로 가는 방법이 6이기 때문에 Dist[2][3]는 6로 바꿔줍니다.

 

플로이드-워셜 알고리즘이 끝나면 각 정점들을 거치는 경우를 계산한 것을 확인할 수 있습니다.

 

Dist[i][j]는 i에서 j로 가는 경우 최단 경로의 값들입니다.

 

위의 예시를 이용한 플로이드-워셜 알고리즘 파이썬 코드입니다.

import sys

INF = sys.maxsize

def Floyd_Warshall():
    dist = [[INF]*n for i in range(n)] # 최단 경로를 담는 배열

    for i in range(n): # 최단 경로를 담는 배열 초기화
        for j in range(n):
            dist[i][j] = a[i][j]

    for k in range(n): # 거치는 점
        for i in range(n): # 시작점
            for j in range(n): # 끝점
                # k를 거쳤을 때의 경로가 더 적은 경로
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

n = 4 # 정점 수
a = [[0, 2, INF, 4],[2, 0, INF, 5],[3, INF, 0, INF],[INF, 2, 1, 0]]

dist = Floyd_Warshall()

for i in range(n):
    for j in range(n):
        print(dist[i][j],end=' ')
    print()