플로이드 와샬 알고리즘

[참고 사이트]
https://blog.encrypted.gg/1035

https://velog.io/@kimdukbae/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Floyd-Warshall-Algorithm

https://velog.io/@asbazq/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Floyd-Warshall

플로이드 알고리즘

2차원 배열에서 모든 정점 쌍 사이의 최단 거리를 구해주는 알고리즘 입니다.

방향/무방향 그래프 둘다 사용 가능합니다. 또한 음의 가중치인 간선이 존재할 수 있으나 음의 가중 순환(사이클)이 없어야합니다.
해당 방식은 각각의 모든 정점을 기준으로 돌아가며, 최단거리를 계산하여 가중치 합이 적은 경우를 계속 갱신하여 최단 거리를 구합니다.
이러한 방식으로 인해 삼중 for문으로 구현합니다. 그래서 전체적으로 O(v^3)의 시간 복잡도가 걸리고, 다익스트라보다 비교적 구현이 쉽습니다.

특징

• 방향/무방향 그래프 모두 사용 가능
• 음의 가중치를 계산가능함(음의 가중 사이클은 불가)
• 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우 사용
• 다익스트라에 비해 코드가 짧아 구현이 쉽다.(for문 3개)
• 단계마다 '거쳐 가는 노드'를 기준으로 최단 거리 테이블을 갱신하는 방식으로 동작
  (판단되지 않은 거리는 무한으로 초기화)
• 2차원 테이블에 최단 거리 정보를 저장
  (모든 지점에서 다른 모든 지점까지의 최단 거리를 저장해야 하기 때문이다.)
• 플로이드 워셜 알고리즘은 DP 알고리즘에 속한다. 왜냐하면 만약 노드의 개수가 N개라고 할 때, N번 만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신하기 때문이다.
• 3중 for문으로인해 시간 복잡도는 O(v^3)이다

작동 순서(그림)

[준비] 그래프의 노드와 간선에 따라 최단 거리 테이블을 갱신

1. 1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신

2. 2번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신

3. 해당 과정을 반복한다(3, 4) 정점을 거쳐 가는 경우 중 최단 거리로 테이블을 갱신

완성!

파이썬 기준 플로이드 와샬 구현

import sys

input = sys.stdin.readline
INF = int(1e9)

# 노드의 개수(n)과 간선의 개수(m) 입력
n = int(input())
m = int(input())

# 2차원 리스트 (그래프 표현) 만들고, 무한대로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
    # A -> B로 가는 비용을 C라고 설정
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과를 출력
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if graph[a][b] == INF:
            print('INFINITY', end=' ')
        else:
            print(graph[a][b], end=' ')
    print()

# 예시 입력
# 4
# 7
# 1 2 4
# 1 4 6
# 2 1 3
# 2 3 7
# 3 1 5
# 3 4 4
# 4 3 2

왜 플로이드 알고리즘을 쓰는가?

그러면 왜 정점의 최단거리를 구하기위해 다익스트라 알고리즘이 아니라 시간 복잡도가 더 높은 플로이드 와샬 알고리즘을 쓸까요?
→ 다익스트라의 경우 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘입니다. 그러나 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우 씁니다.