[Coding Test][Python][Shortest Path] Floyd-Warshall 알고리즘 개념 및 예제

Floyd - Warshall에 앞서 Dijkstra 알고리즘을 먼저 보고 오시면 좋습니다.

[Coding Test][Python][Shortest Path] Dijkstra Algorithm(다익스트라) 개념 및 예제

 

1. Floyd - Warshall(플로이드 워셜) 알고리즘 이란?

Dijkstra 알고리즘은 한 지젬에서 다른 지점까지로 가는 최단거리만 제공하기 때문에, 모든 지점의 최단거리를 구하기 위해서는 각각의 지점에 대한 Dijkstra 알고리즘을 한번씩 수행해야합니다. 하지만 Floyd - Warshall 알고리즘은 여기에 더 나아가 모든 Vertex에서 다른 모든 Vertex 까지의 최단경로를 구하는 알고리즘입니다. 다익스트라 알고리즘과 플로이드 워셜 알고리즘의 아이디어는 유사한데, A -> B로 가는 경로보다 A -> -X -> B로 가는 경로가 더 짧다면 그 경로를 선택하는 것이 Floyd - Warshall 알고리즘입니다.

시간 복잡도는 $O(V^3)$으로 Vertex의 수가 적은 경우 효과적입니다. 또한, Floyd - Warshall 알고리즘은 Dijkstra 알고리즘과 달리 음수 Weight를 허용합니다.

알고리즘 동작 과정

1)  Distance 배열 초기화

$V^2$ 크기의 dist 배열의 모든 값을 INF값으로 초기화합니다.

2)  Graph의 Edge 초기화

각 Edge에 적힌 Weight를 dist 배열에 넣어줍니다.

이 때, 자기 자신으로 가는 거리는 0으로 넣어줍니다.

3)  경유했을때의 값 비교

Vertex 1부터 시작하여 N번 Vertex가지 순서대로 경유했을 때를 가정합니다.

모든 쌍 $(i, j)$에 대해 Vertex 1번을 경유하는 것이 더 좋은 경우 그 값을 갱신합니다. 즉, $dist[i][j] > dist[i][1] + dist[1][j]$를 만족하는 경우 값을 갱신합니다 ( 1번 Vertex를 경유하는 상황을 가정하였으니, 모든 Vertex를 경유한다고 가정한다면 for loop을 추가하고 k번 Vertex를 경유하는 상황을 만들면 됩니다.)

4)  경유 상황을 반복

경유하는 상황을 2번 노드에 대해 반복하면 값이 아래처럼 새롭게 갱신되게 됩니다.

요약하자면, Floyd - Warshall 알고리즘은 경유할 점을 Vertex 1부터 Vertex N으로 확장해가며 $dist[i][j]$가 $dist[i][k] + dist[k][j]$보다 크다면 갱신해주는 알고리즘입니다.
코드에서 k, i, j 순서에 유의하세요 ! 
시간복잡도는 $O(V^3)$이므로 굉장히 비효율적이지만, Vertex의 수가 많지 않거나 모든 쌍에 대한 최단거리를 구해야만 할 때 사용해야합니다.

2. Floyd - Warshall Algorithm  구현 및 예제

아래 그래프에서 모든 Vertex에서 시작한 최단 거리를 구하여라.

.

1) dist 배열 및 Edge 초기화

V = 6
INF = float('inf')
edges = [
    [1, 2, 2],
    [1, 3, 5],
    [1, 4, 1],
    [2, 3, 3],
    [2, 4, 2],
    [3, 4, 3],
    [3, 5, 1],
    [3, 6, 5],
    [4, 5, 1],
    [5, 6, 2]
]
# 초기 dist는 INF 값으로 초기화
dist = [ [INF] * (V+1) for _ in range(V+1)]

for edge in edges:
    u, v, d = edge
    dist[u][v] = d
    dist[v][u] = d

# 자기 자신으로 가는 Edge는 0
for i in range(1, V+1):
    dist[i][i] = 0

2) Floyd - Warshall 알고리즘

def floyd_warshall(dist):
    for k in range(1, N+1):
        for i in range(1, N+1):
            for j in range(1, N+1):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
    return dist

3) 결과 확인

dist = floyd_warshall(dist)

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

0 2 3 1 2 4
2 0 3 2 3 5
3 3 0 2 1 3
1 2 2 0 1 3
2 3 1 1 0 2
4 5 3 3 2 0