1. 최단 경로 탐색

알고리즘 이름 그대로 가장 짧은 거리를 찾는 알고리즘이다. 최단 경로를 탐색해야 하는 유형의 문제는 다양하게 주어지는데, 모든 지점에서 모든 지점으로의 최단 거리 구하기나 한 특정 지점에서 모든 지점으로의 최단거리 혹은, 어느 특정 지점에서 한 특정 지점으로의 최단거리 등등의 문제 유형들이 있다. 최단 경로 탐색 알고리즘은 BFS, 플로이드, 벨만-포드, 다익스트라가 대표적인데 이번에는 플로이드-워셜에 대해서 살펴보겠다.

2. 그래프

BFS와 다익스트라 알고리즘의 차이는 그래프의 가중치가 있느냐, 없느냐의 차이가 대표적이었다. 플로이드 워셜 알고리즘이 다익스트라 알고리즘과 다른 점은, 가중치가 주어질 때 다익스트라와는 달리 음의 정수(음의 사이클은 제외: 다른 노드를 통해서 자신에게 돌아왔을 경우 음의 거리가 나오는 경우)도 사용가능하다는 특징이 있으며, '모든 정점'에서 '모든 정점'으로 가는 최단 거리를 구할 때 사용할 수 있는 알고리즘이다.
모든 정점에서 모든 정점으로의 거리를 구하기 때문에 2차원 인접 행렬을 통해서 해결을 하며, 첫번째 노드부터 마지막 노드까지 모든 노드들을 출발점으로 삼아서 방문 가능한 모든 노드를 방문하면서 더 짧은 거리가 있으면 짧은 거리로 업데이트가 일어난다. 노드가 10개라면, 노드 10개를 하나하나 순회하면서 출발점으로 삼고 방문 가능한 모든 노드들을 탐색해 나간다.

3. 점진적 업데이트

플로이드 워셜 알고리즘은 짧은 거리를 업데이트 할 때 점진적인 업데이트를 통해 알고리즘의 당위성을 입증한다는 특징이 있다. 이런 점진적인 업데이트를 통한 문제 해결은 다이니막 프로그래밍의 특징이다.
업데이트는 2차원 배열을 활용하며, 'graph[2][3](2행3열) = 2'의 뜻은, 2에서 3으로 갈 수 있는 거리의 가중치는 '2'라는 것이다.
업데이트 순서는 아래와 같다.

1. 자신에게서 자신으로 가는 가중치는 모두 0으로 2차원 배열에 초기화를 하고 시작한다.(자신에게서 자신으로는 가중치가 없다)
2. 그리고 한 번에 갈 수 있는 모든 경로를 2차원 배열에 업데이트를 한다.
3. 이제부터 최소 1번을 지나쳐서 가야하는 경로를 구해야 하는데, 중간 지점(꼭지점 혹은 정점이라고 하자) 'k'를 지나쳐 가는 경우를 모두 구한다. 예로 A 에서 C로 한 번에 갈 수 있는 경우와, A에서 C를 갈 때 B를 거쳐서 가는 경우가 있다고 가정해보자. 이미 한 번에 걸쳐 갈 수 있는 모든 경우의 수를 업데이트를 했다.(한 번에 갈 수 있는 경우의 수: A-B, B-C, A-C) 'A-C'는 갈 수가 없어 가중치가 무한대였지만, 'A-B'로 갈 수가 있고 'B-C'로 갈 수가 있다면 경로가 생기게 되어 이제 'A-C'는 경로가 생겼다. 그래서 " 'A-C' = min('A-C', 'A-B'+ 'B-C') ", 즉 거쳐서 갈 경우의 거리가 더 짧은 경우에는 짧은 거리로 'A-C'의 값을 업데이트 한다. 이처럼 'A-C'를 업데이트 할 수 있는 이유는 앞서 A-B, B-C, A-C의 경우의 수를 거치면서 업데이트가 되었다는 전제가 있기 때문이다.
4. 같은 말을 계속 반복하는데, 업데이트를 할 수 있는 이유는 이미 한 번에 걸쳐 갈 수 있는 모든 거리는 이미 업데이트가 되었다는 전제를 두고 있기 때문이다. 다시 말해 'A-C', 'A-B', 'B-C'는 이미 최적화 업데이트가 되어 있다는 것을 전제한다는 것이다.
5. 'k'를 정점으로 지나치는 모든 경우의 수를 모두 업데이트 한 후, 위의 3, 4를 반복하면서 업데이트를 한다.

3.1 오류 발생

점진적인 업데이트라는 특징 때문에 플로이드 워셜 문제를 해결할 때 실수를 하게 된다.
보통 플로이드 워셜 문제는 중간 정점을 지나치며 방문할 수 있는 노드들을 비교하기 때문에 3중 for 반복문을 사용한다.

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):

위와 같이 반복문을 사용할 시, 정점을 제일 바깥 반복문에 두고 정점 'k'를 지나치는 경우의 수를 모두 구한 다음, 그 다음의 정점 k를 거치는 모든 경우의 수를 업데이트 해야한다. 하지만 중간이나 안쪽 반복문에 정점을 위치시키면 정점 'k'가 계속 바뀌면서 점진적인 업데이트를 하지 못하게 됨으로써 올바른 해결을 하지 못하게 된다.

하지만 이렇게 생각할 수 있다. 어차피 모든 노드를 거쳐서 모든 경우의 수를 비교하는데 오류가 일어날 수 있어? 순서가 상관없잖아?
물론 4개를 지나쳐 도착한 것을 먼저 업데이트 하더라도, 2개를 지나친 거리가 짧을 경우 업데이트 하면 된다. 하지만 4번을 거치는 것을 먼저 업데이트 하게 된다면 그 시점에서 이미 오류다. 왜냐하면 4번을 지나칠 때 2번을 지나치는 것이 업데이트 되지 않은 상태이기에, 4번을 지나치며 업데이트 한 경우의 당위성을 입증하지 못하게 된다.
정점을 바꿔가면서 업데이트 하더라도 어차피 모든 경우의 수를 업데이트 한다면, 코드로 하나하나 모든 경우의 수를 코딩하기엔 너무 길어지기 마련이다. 그렇게 하려면 굳이 플로이드 워셜 알고리즘을 사용할 필요가 없다. 알고리즘을 사용하는 이유는 연산 횟수에 있어서 순서가 없는 모든 경우의 수를 고려하는 코드보다 빠르기 때문이다. 빠르면서도 당위성을 입증할 수 있는 알고리즘이 플로이드 워셜 알고리즘이다.

4. 코드 보기

문제:
n개의 노드와 노드를 잇는 간선 m개가 주어졌을 때 모든 정점에서 모든 정점으로의 최단 거리를 구하시오.
갈 수 없다면 'M'으로 출력하시오.
n, m 그리고 간선은 input으로 입력되며, 간선은 's에서 e까지의 거리는 v'로 입력된다.(s e v)
입력:
6 9
1 2 6
1 3 4
2 1 2
2 3 3
2 5 5
3 4 5
4 2 7
4 5 5
6 4 9

def floyd(n, m , board):
    for k in range(1, n + 1): # 정점
        for i in range(1, n + 1): # 출발점
            for j in range(1, n + 1): # 도착점
                board[i][j] = min(board[i][j], board[i][k] + board[k][j]) # 정점을 거치지 않은 경우와 거치는 경우 중 값이 낮은 거리를 업데이트
    for x in range(1, n + 1):
        for y in range(1, n + 1):
            if board[x][y] == 1e9: # 무한이라면 'M'으로 출력
                print('M', end=' ')
            else:
                print(board[x][y], end= ' ')
        print()
if __name__ == '__main__':
    n, m = map(int, input().split())
    board = [[1e9] * (n + 1) for _ in range(n + 1)] # 작은 값을 업데이트 하기에 상대적으로 큰 수 입력
    for i in range(m):
        s, e, v = map(int, input().split()) # s에서 e까지 거리는 v
        board[s][e] = v
    for i in range(n + 1): # 자신에게서 자신으로의 값은 '0'으로 초기화
        board[i][i] = 0
    floyd(n, m , board)
출력:
0 6 4 9 11 M 
2 0 3 8 5 M 
14 12 0 5 10 M 
9 7 10 0 5 M 
M M M M 0 M 
18 16 19 9 14 0

잘못된 코드:
반복문의 위치만 바꿨을 뿐이지만 점진적인 순서로 업데이트 된 것이 아니기에 출력이 다르게 나온다.

def floyd(n, m , board):
    for i in range(1, n + 1):
        for k in range(1, n + 1):
            for j in range(1, n + 1):
                # k가 계속 바뀜으로써 board[i][k]의 당위성이 입증되지 않는다. board[i][u] + board[u][k]의 경우를 입증하지 못하기 때문이다.
                board[i][j] = min(board[i][j], board[i][k] + board[k][j])
    for x in range(1, n + 1):
        for y in range(1, n + 1):
            if board[x][y] == 1e9:
                print('M', end=' ')
            else:
                print(board[x][y], end= ' ')
        print()
if __name__ == '__main__':
    n, m = map(int, input().split())
    board = [[1e9] * (n + 1) for _ in range(n + 1)]
    for i in range(m):
        s, e, v = map(int, input().split()) # s에서 e까지 거리는 v
        board[s][e] = v
    for i in range(n + 1):
        board[i][i] = 0
    floyd(n, m , board)
출력:
0 6 4 9 11 M 
2 0 3 8 5 M 
M 12 0 5 10 M # 3에서 1로 갈 수 있는 경우의 수를 업데이트 하지 못한다.(3 -> 4 -> 2 -> 1 : 14)
9 7 10 0 5 M 
M M M M 0 M 
18 16 19 9 14 0