Floyd-Warshall (플로이드 워셜 - 최단거리 알고리즘)

개념

• 컴퓨터 과학에서 플로이드 워셜 알고리즘은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다.
• "모든 노드"에서 다른 "모든 노드" 까지 최단경로 모두 계산
• 모든 정점 마다 거쳐갈 때 상황을 가정하여, 최단거리를 완화해서 나간다는 점에서 dp 유형에 해당하는 알고리즘이다.
• 노드 k를 경유해 가는 경우를 확인
• (A --> B) 와 (A --> K --> B) 뭐가 더 짧은지 확인한다.

k = 1 일 때,

4번 --> 2번 이동 불가능(INF) 했지만, 1을 경유하면, 4 --> 1 --> 2 값 5로 갱신
4번 --> 5번 이동 불가능(INF) 했지만, 1을 경우하면, 4 --> 1 --> 5 값 -2로 갱신

새롭게 갱신된 그래프를 통해, k = 2 일 때,

1번 --> 4번 이동 불가능(INF) 했지만, 2을 경유하면, 1 --> 2 --> 4 값 4로 갱신
3번 --> 4번 이동 불가능(INF) 했지만, 2을 경유하면, 3 --> 2 --> 5 값 5로 갱신
3번 --> 5번 이동 불가능(INF) 했지만, 2을 경유하면, 3 --> 2 --> 5 값 11로 갱신

새롭게 갱신된 그래프를 통해, k = 3 일때,

4번 --> 2번 5의 비용을 소모 했지만, 3을 경유하면, 4 --> 3 --> 2 값 -1로 갱신

새롭게 갱신된 그래프를 통해, k = 4 일때,

1번 --> 3번 8의 비용을 소모 했지만, 4을 경유하면, 1 --> 4 --> 3 값 -1로 갱신
2번 --> 1번 이동 불가능(INF)했지만, 4을 경유하면, 2--> 4 --> 1 값 3로 갱신
2번 --> 3번 이동 불가능(INF)했지만, 4을 경유하면, 2 --> 4 --> 3 값 -4로 갱신
2번 --> 5번 7의 비용을 소모 했지만, 4을 경유하면, 2 --> 4 --> 5 값 -1로 갱신
3번 --> 1번 이동 불가능(INF)했지만, 4을 경유하면, 3 --> 4 --> 1 값 7로 갱신
3번 --> 5번 11의 비용을 소모 했지만, 4을 경유하면, 3 --> 4 --> 5 값 3로 갱신
5번 --> 1번 이동 불가능(INF)했지만, 4을 경유하면, 5 --> 4 --> 1 값 8로 갱신
5번 --> 2번 이동 불가능(INF)했지만, 4을 경유하면, 5 --> 4 --> 2 값 5로 갱신
5번 --> 3번 이동 불가능(INF)했지만, 4을 경유하면, 5 --> 4 --> 3 값 1로 갱신

새롭게 갱신된 그래프를 통해, k = 5 일때,

1번 --> 2번 3의 비용을 소모 했지만, 4을 경유하면, 1 --> 5 --> 2 값 1로 갱신
1번 --> 3번 -1의 비용을 소모 했지만, 4을 경유하면, 1 --> 5 --> 3 값 -3로 갱신
1번 --> 4번 4의 비용을 소모 했지만, 4을 경유하면, 1 --> 5 --> 4 값 2로 갱신

실제 문제를 해결하는 순서

정점의 개수가 500개를 넘어가지 않는지 확인한다.
넘어간다면 다익스트라를 써서 해결할 수 있는지 확인한다.

• 입력 값을 통해 인접 행렬(가중치 행렬)을 생성한다.
• 인접행렬의 모든 값은 INF로 초기화 한다.
• 대각선 값 (i=j) 0으로 넣어준다 (이 것을 빼먹으면 안 된다)
• Edge 값을 입력한다.
• I K J 3 중 반복문을 통해 가중치를 완화시킨다.

https://www.acmicpc.net/problem/11404

import sys

input = sys.stdin.readline

n = int(input())
m = int(input())

INF = 1000_000_000

dist = [[INF for j in range(n + 1)] for i in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            dist[i][j] = 0

for i in range(m):
    u, v, w = map(int, input().split())
    #  시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.
    dist[u][v] = min(dist[u][v], w)


def floyd():
    for k in range(1, n + 1):
        for a in range(1, n + 1):
            for b in range(1, n + 1):
                dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])


if __name__ == '__main__':

    floyd()

    for i in range(1, n + 1):
        line = []
        for j in range(1, n + 1):
            if dist[i][j] == INF:
                line.append(0)
            else:
                line.append(dist[i][j])
        print(' '.join(map(str, line)))