모든 쌍 최단 경로 찾기 (플로이드 워셜 알고리즘)

동적 계획 알고리즘 (Dynamic Programming; DP)

입력 크기가 작은 부분 문제들을 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘

분할 정복 알고리즘과 유사한 부분이 많으나 DP는 같은 부분 문제를 다시 풀지 않는다는 점, 부분 문제의 해를 중복 사용한다는 점에서 정복 기법과 다름

참고) 알기 쉬운 알고리즘

 

---

모든 쌍 최단 경로 (All Pairs Shortest Paths) 찾기

각 쌍의 점 사이의 최단 경로

다익스트라 알고리즘을 이용한다면 각 점을 시작점으로 정하여 다익스트라 알고리즘 수행

플로이드-워셜 알고리즘

워셜(Warshall) : 그래프에서 모든 쌍의 경로 존재 여부를 찾아내는 동적 계획 알고리즘을 제안

플로이드(Floyed) : 워셜의 알고리즘을 변형하여 모든 쌍 최단 경로를 찾는 알고리즘을 고안

∴ 플로이드-워셜 알고리즘 : 모든 쌍 최단 경로를 찾는 동적 계획 알고리즘

플로이드-워셜 알고리즘은 매우 간단하여 다익스트라 알고리즘보다 효율적

 

동적 계획 알고리즘으로 모든 쌍 최단 경로 문제를 해결하기 위해 먼저 가장 작은 부분문제를 찾아야 함

가장 작은 부분 문제 : 3개의 점이 있는 경우

아래와 같이 a에서 c까지의 최단 경로를 찾을 때 2가지의 경로 중 짧은 경로를 선택

경로 1 : a -> c

경로 2 : a -> b -> c (점 b 경유)

참고) 알기 쉬운 알고리즘

 

 

그래프의 점이 1, 2, 3, ..., n일 때

D_ij^k = 점 {1, 2, ..., k}를 경유 가능한 점으로 고려하여, 점 i에서 점 j까지의 모든 경로 중에서 가장 짧은 경로의 거리

점 1에서 점 k까지의 모든 점을 반드시 경유하는 경로를 의미하는 게 아님.

k까지의 점들을 경유한 경로 중 가장 짧은 거리를 구하는 것. 즉, k를 경유했을 수도, 1만 경유했을 수도, 1, 2, k만 경유했을 수도, 아니면 다 경유하지 않고 곧바로 점 i에서 점 j까지 갔을 수도 있다는 의미

k=0인 경우, 점 0은 그래프에 없으므로 어떤 점도 경유하지 않았다는 것을 의미. 즉, D_ij⁰ = 간선 (i, j)의 가중치

 

 D_ij¹ = 점 i에서 점 j까지 점 1을 경유하는 경우와 직접 가는 경로 중 짧은 경로의 거리

(단, i ≠ 1, j ≠ 1)

참고) 알기 쉬운 알고리즘

 

 

D_ij² = 점 i에서 점 2를 경유하여 j로 가는 경로의 거리와 D_ij¹ 중 짧은 경로의 거리

(점 2를 경유하는 경로의 거리 = D_i2¹ + D_2j¹)

(단, i ≠ 2, j ≠ 2)

참고) 알기 쉬운 알고리즘

 

 

D_ij^k = 점 i에서 점 k를 경유하여 j로 가는 경로의 거리와 D_ij^k-1 중 짧은 경로의 거리

(점 k를 경유하는 경로의 거리 = D_ik^k-1 + D_kj^k-1)

(단, i ≠ k, j ≠ k)

참고) 알기 쉬운 알고리즘

 

 

D[i, j]를 계산하기 위해서는 먼저 부분문제 D[i, k]와 D[k, j] 가 계산되어 있어야 함

(D[i, j] = 점 i에서 점 j까지의 최단 경로)

참고) 알기 쉬운 알고리즘

 

---

예제

참고) 알기 쉬운 알고리즘

 

 

▶ k=1 일 때 (k ≠ i ≠ j)

D[2, 3] = 2 → 3까지 바로 가는 경로와 1을 경유한 경로((2 → 1) + (1 → 3)) 중 더 짧은 경로

            = min{D[2, 3], D[2, 1]+D[1, 3]} = min{1, ∞+2} = 1

D[2, 4] = min{D[2, 4], D[2, 1]+D[1, 4]} = min{∞, ∞+5} = ∞

D[2, 5] = min{D[2, 5], D[2, 1]+D[1, 5]} = min{4, ∞+∞} = 4

D[3, 2] = min{D[3, 2], D[3, 1]+D[1, 2]} = min{3, 1+4} = 3

D[3, 4] = min{D[3, 4], D[3, 1]+D[1, 4]} = min{1, 1+5} = 1

D[3, 5] = min{D[3, 5], D[3, 1]+D[1, 5]} = min{2, 1+∞} = 2

D[4, 2] = min{D[4, 2], D[4, 1]+D[1, 2]} = min{∞, -2+4} = 2  // update

D[4, 3] = min{D[4, 3], D[4, 1]+D[1, 3]} = min{∞, -2+2} = 0  // update

D[4, 5] = min{D[4, 5], D[4, 1]+D[1, 5]} = min{2, -2+∞} = 2

D[5, 2] = min{D[5, 2], D[5, 1]+D[1, 2]} = min{-3, ∞+4} = -3

D[5, 3] = min{D[5, 2], D[5, 1]+D[1, 3]} = min{3, ∞+2} = 3

D[5, 4] = min{D[5, 2], D[5, 1]+D[1, 4]} = min{1, ∞+5} = 1

참고) 알기 쉬운 알고리즘

 

 

▶ k=2 일 때 (k ≠ i ≠ j)

D[1, 3] = min{D[1, 3], D[1, 2]+D[2, 3]} = min{2, 4+1} = 2

D[1, 4] = min{D[1, 4], D[1, 2]+D[2, 4]} = min{5, 4+∞} = 5

D[1, 5] = min{D[1, 5], D[1, 2]+D[2, 5]} = min{∞, 4+4} = 8  // update

D[3, 1] = min{D[3, 1], D[3, 2]+D[2, 1]} = min{1, 3+∞} = 1

D[3, 4] = min{D[3, 4], D[3, 2]+D[2, 4]} = min{1, 3+∞} = 1

D[3, 5] = min{D[3, 5], D[3, 2]+D[2, 5]} = min{2, 3+4} = 2

D[4, 1] = min{D[4, 1], D[4, 2]+D[2, 1]} = min{-2, 2+∞} = -2

D[4, 3] = min{D[4, 3], D[4, 2]+D[2, 3]} = min{0, 2+1} = 0

D[4, 5] = min{D[4, 5], D[4, 2]+D[2, 5]} = min{2, 2+4} = 2

D[5, 1] = min{D[5, 1], D[5, 2]+D[2, 1]} = min{∞, -3+∞} = ∞

D[5, 3] = min{D[5, 3], D[5, 2]+D[2, 3]} = min{3, -3+1} = -2  // update

D[5, 4] = min{D[5, 4], D[5, 2]+D[2, 4]} = min{1, -3+∞} = ∞

참고) 알기 쉬운 알고리즘

 

 

▶ k=3 일 때 (k ≠ i ≠ j)

D[1, 2] = min{D[1, 2], D[1, 3]+D[3, 2]} = min{4, 2+3} = 4

D[1, 4] = min{D[1, 4], D[1, 3]+D[3, 4]} = min{5, 2+1} = 3  // update

D[1, 5] = min{D[1, 5], D[1, 3]+D[3, 5]} = min{8, 2+2} = 4  // update

D[2, 1] = min{D[2, 1], D[2, 3]+D[3, 1]} = min{∞, 1+1} = 2  // update

D[2, 4] = min{D[2, 4], D[2, 3]+D[3, 4]} = min{∞, 1+1} = 2  // update

D[2, 5] = min{D[2, 5], D[2, 3]+D[3, 5]} = min{4, 1+2} = 3  // update

D[4, 1] = min{D[4, 1], D[4, 3]+D[3, 1]} = min{-2, 0+1} = -2

D[4, 2] = min{D[4, 2], D[4, 3]+D[3, 2]} = min{2, 0+3} = 2

D[4, 5] = min{D[4, 5], D[4, 3]+D[3, 5]} = min{2, 0+2} = 2

D[5, 1] = min{D[5, 1], D[5, 3]+D[3, 1]} = min{∞, -2+1} = -1  // update

D[5, 2] = min{D[5, 2], D[5, 3]+D[3, 2]} = min{-3, -2+3} = -3

D[5, 4] = min{D[5, 4], D[5, 3]+D[3, 4]} = min{1, -2+1} = -1  // update

참고) 알기 쉬운 알고리즘

 

 

▶ k=4 일 때 (k ≠ i ≠ j)

D[1, 2] = min{D[1, 2], D[1, 4]+D[4, 2]} = min{4, 3+2} = 4

D[1, 3] = min{D[1, 3], D[1, 4]+D[4, 3]} = min{2, 3+0} = 2

D[1, 5] = min{D[1, 5], D[1, 4]+D[4, 5]} = min{4, 3+2} = 4

D[2, 1] = min{D[2, 1], D[2, 4]+D[4, 1]} = min{2, 2-2} = 0  // update

D[2, 3] = min{D[2, 3], D[2, 4]+D[4, 3]} = min{1, 2+0} = 1

D[2, 5] = min{D[2, 5], D[2, 4]+D[4, 5]} = min{3, 2+2} = 3

D[3, 1] = min{D[3, 1], D[3, 4]+D[4, 1]} = min{1, 1-2} = -1  // update

D[3, 2] = min{D[3, 2], D[3, 4]+D[4, 2]} = min{3, 1+2} = 3

D[3, 5] = min{D[3, 5], D[3, 4]+D[4, 5]} = min{2, 1+2} = 2

D[5, 1] = min{D[5, 1], D[5, 4]+D[4, 1]} = min{-1, -1-2} = -3  // update

D[5, 2] = min{D[5, 2], D[5, 4]+D[4, 2]} = min{-3, -1+2} = -3

D[5, 3] = min{D[5, 3], D[5, 4]+D[4, 3]} = min{-2, -1+0} = -2

참고) 알기 쉬운 알고리즘

 

 

▶ k=5 일 때 (k ≠ i ≠ j)

D[1, 2] = min{D[1, 2], D[1, 5]+D[5, 2]} = min{4, 4-3} = 1  // update

D[1, 3] = min{D[1, 3], D[1, 5]+D[5, 3]} = min{2, 4-2} = 2

D[1, 4] = min{D[1, 4], D[1, 5]+D[5, 4]} = min{3, 4-1} = 3

D[2, 1] = min{D[2, 1], D[2, 5]+D[5, 1]} = min{0, 3-3} = 0

D[2, 3] = min{D[2, 3], D[2, 5]+D[5, 3]} = min{1, 3-2} = 1

D[2, 4] = min{D[2, 4], D[2, 5]+D[5, 4]} = min{2, 3-1} = 2

D[3, 1] = min{D[3, 1], D[3, 5]+D[5, 1]} = min{-1, 2-3} = -1

D[3, 2] = min{D[3, 2], D[3, 5]+D[5, 2]} = min{3, 2-3} = -1  // update

D[3, 4] = min{D[3, 4], D[3, 5]+D[5, 4]} = min{1, 2-1} = 1

D[4, 1] = min{D[4, 1], D[4, 5]+D[5, 1]} = min{-2, 2-3} = -2

D[4, 2] = min{D[4, 2], D[4, 5]+D[5, 2]} = min{2, 2-3} = -1  // update

D[4, 3] = min{D[4, 3], D[4, 5]+D[5, 3]} = min{0, 2-2} = 0

참고) 알기 쉬운 알고리즘

시간복잡도

다익스트라 알고리즘 : O(n²)

플로이드-워셜 알고리즘 : O(n³)

각 k에 대해서 모든 i, j 쌍에 대해 계산되므로, 총 n*n*n = n³

(다익스트라 알고리즘을 n(각 점의 개수)번 사용할 때의 시간 복잡도와 동일)

 

 

import copy

INF = float('inf')

def shortest_path_floyd(V, adj):
    N = len(V)
    dist = copy.deepcopy(adj)
    via = [[-1] * N for i in range(N)]
    
    # k : 경유지
    for k in range(N):
        for i in range(N):
            for j in range(N):
                # print("i : ", i, "j : ", j , "k : ", k)
                if i != k and j != k and i != j and dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    via[i][j] = k
                    
    return dist, via

def find_path(path, i, j):
    k = path[i][j]
    if k < 0:
        return []
    
    return find_path(path, i, k) + [k] + find_path(path, k, j)


# 실행
if __name__ == '__main__':
    
    vertex = ['A', 'B', 'C', 'D', 'E']
    weight = [[  0,   4,   2,   5, INF],
              [INF,   0,   1, INF,   4],
              [  1,   3,   0,   1,   2],
              [ -2, INF,   0 ,  0,   2],
              [INF,  -3,   3,   2,   0]]

    n = len(vertex)
    dist, via = shortest_path_floyd(vertex, weight)

    for i in range(n):
        print(dist[i])
        
    for i in range(n):
        for j in range(n):
            if i != j:
                path = [i] + find_path(via, i, j) + [j]
                path_str = [vertex[node] for node in path]
                print(f"{vertex[i]} to {vertex[j]} : {dist[i][j]:3d}, ({path_str})")

 

실행 결과