BOJ 11404 플로이드 (플로이드-워셜 알고리즘)

그래프 최소거리 문제 중 각 정점에서 다른 모든 정점으로의 최소거리를 구하는 문제를 푸는 알고리즘. 백준의 11404 문제가 대표적인 문제이다.

구현은 간단하다. 시작점, 끝점, 중간점을 기준으로 for문을 작성하면 된다. 모든 정점에 대해 3번 반복문이 작성되므로 시간복잡도는 $O(V^3)$이다. 유일하게 주의할 점은 중간점이 첫 for문이어야 한다는 점이다.

for mid in range(1, n + 1):
    for start in range(1, n + 1):
        for end in range(1, n + 1):
            if distance[start][end] > (distance[start][mid] + distance[mid][end]):
                distance[start][end] = distance[start][mid] + distance[mid][end]

문제 답 코드

import sys

input = sys.stdin.readline


def main():
    n = int(input())
    m = int(input())
    INF = int(1e9)
    distance = [[INF] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        distance[i][i] = 0
    for _ in range(m):
        start, end, cost = map(int, input().split())
        distance[start][end] = min(distance[start][end], cost)

    # floyd-warshall
    for mid in range(1, n + 1):
        for start in range(1, n + 1):
            for end in range(1, n + 1):
                if distance[start][end] > (distance[start][mid] + distance[mid][end]):
                    distance[start][end] = distance[start][mid] + distance[mid][end]

    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if distance[i][j] == INF:
                distance[i][j] = 0
        print(*distance[i][1:])


if __name__ == '__main__':
    main()