코딩테스트 - 플로이드 워셜

다익스트라 알고리즘에서도 언급했듯이 플로이드 워셜은 음수를 갖는 간선에서도 최단거리를 구할 수 있는 알고리즘이라고 한다.

1. 플로이드 워셜
   다익스트라 알고리즘은 특정 노드에서 시작해서 다른 노드까지의 최단경로를 구하는 알고리즘이다. 하지만 플로이드 워셜은 모든 정점으로부터 모든 정점까지의 최단경로를 구하는 알고리즘이다. 또한 다이나믹 프로그래밍을 사용한다.
   작동방식은

- 인접 행렬로 그래프 표시(단, 연결되어 있지 않은 경우는 INF로 표시)
- 인접행렬을 이용하여 특정 노드를 경유하여 가는 값이 기존 거리 값보다 작으면 갱신
- 모든 노드를 경유한 경우도 고려해야 하므로 모든 노드에 대해 2번 작업 반복

라고 한다.

위에 그림은 플로이드 워셜에 점화식이다.

2. Code

다익스트라 알고리즘에서 다룬 것과 같은 그래프를 사용하겠다.

graph = {'A': {'B': 6, 'D': 2, 'F': 3},
         'B': {'A': 3, 'C': 4, 'D': 1},
         'C': {'B': 4, 'E': 1, 'F': 5},
         'D': {'A': 2, 'B': 1, 'F': 2, 'G': 8},
         'E': {'C': 1, 'F': 1},
         'F': {'A': 3, 'E': 1, 'G': 1},
         'G': {'D': 8, 'F': 1}}


def floyd(graph):
    # 알파벳을 숫자로 변환하기 위한 변수 생성
    alpha_to_num = {key: index for index, key in enumerate(graph.keys())}

    dists = [[float("INF")] * 7 for _ in range(7)]

	# 자기 자신까지 최소거리 = 0
    for i in range(7):
        dists[i][i] = 0

	# graph에 맞게 거릿값 변경
    for key, value in graph.items():
        key_num = alpha_to_num[key]
        for value_key, value_value in value.items():
            value_key_num = alpha_to_num[value_key]
            if value_value < dists[key_num][value_key_num]:
                dists[key_num][value_key_num] = value_value
                dists[value_key_num][key_num] = value_value

	# 점화식에 의거한 식
    for k in range(7):
        for i in range(7):
            for j in range(7):
                dists[i][j] = min(dists[i][j], dists[i][k] + dists[j][k])

    return dists


print(floyd(graph))

출력

[[0, 3, 5, 2, 4, 3, 4], 
 [3, 0, 4, 1, 4, 3, 4], 
 [5, 4, 0, 4, 1, 2, 3], 
 [2, 1, 4, 0, 3, 2, 3], 
 [4, 4, 1, 3, 0, 1, 2], 
 [3, 3, 2, 2, 1, 0, 1], 
 [4, 4, 3, 3, 2, 1, 0]]

확실히 이렇게 하면 음수도 비교할 수 있을 것 같다. 방향그래프로 할경우 dists를 초기화 하는 부분에 코드 수정이 필요할 것 같다.