플로이드 워셜 알고리즘

플로이드 워셜 알고리즘

모든 정점에서 모든 정점까지 이동할 때 최소 비용을 얻을 수 있는 알고리즘이다.

모든 정점 사이의 비용을 구하다보니 시간 복잡도는 O(정점의 수 ^ 3) 으로 상당히 높다.

플로우

모든 정점을 대상으로 총 3 번의 중첩 반복문을 실행한다. 가장 외부의 반복문은 이후에 나올 시작 정점, 도착 정점이 반드시 거치게 될 중간 정점을 선택한다. 그 다음 내부의 두 반복문은 시작 정점, 도착 정점을 선택한다.

이를 반복해서 모든 경우를 고려할 수 있다.

너무 생략했나.. 벨만 포드 알고리즘 과 코드만 봐도 쉽게 이해할 수 있을 것이다.

소스 코드

n = int(input())
m = int(input())
INF = float('inf')
board = [[(INF, INF, None) for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):
    f, t, c = map(int, input().split())
    if board[f][t][0] > c:
        path = []
        path.append(f)
        path.append(t)
        board[f][t] = (c, 2, path)
for i in range(n+1):
    board[i][i] = (0, 1, [i])
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if board[i][j][0] > board[i][k][0] + board[k][j][0]:
                board[i][j] = (board[i][k][0] + board[k][j][0], board[i][k][1] + board[k][j][1] - 1, board[i][k][2][:-1] + board[k][j][2])

for i in range(1, n+1):
    for j in range(1, n+1):
        if board[i][j][0] == 0 or board[i][j][0] == INF:
            print(0, end=' ')
        else:
            print(board[i][j][0], end=' ')
    print()

for i in range(1, n+1):
    for j in range(1, n+1):
        cost, len, path = board[i][j]
        if cost == 0 or cost == INF:
            print(0)
        else:
            print(len, ' '.join(list(map(str, path))))