[Python] 백준 1613. 역사 (Floyd Warshall)

플로이드 워셜(Floyd Warshall) 알고리즘

이 알고리즘은 모든 노드 간의 최단거리를 구할 수 있다.

다익스트라, 벨만포드와의 차이점

두 알고리즘은 한 노드에서 다른 모든 노드까지의 최단 거리를 구하지만, 플로이드 워셜은 모든 노드 간의 최단거리를 구함

원리

• 공식: D[i][j] = min(D[i][j], D[i][k] + D[k][j])
• 특정한 노드 k를 거쳐 가는 경우를 고려함
• 이 식을 모든 start, end, k 노드에 대해서 적용해야 하기 때문에 3중 for문으로 구현

특징

음의 가중치가 있더라도 최단 경로 구할 수 있음. 단, 음의 사이클이 존재하면 벨만 포드 사용해야 함.

코드

import sys
from math import inf

input = sys.stdin.readline


def FloydWarshall():
    for k in range(1, n + 1):
        dist[k][k] = 0
        for start in range(1, n + 1):
            for end in range(1, n + 1):
                dist[start][end] = min(dist[start][end], dist[start][k] + dist[k][end])


if __name__ == '__main__':
    n, k = map(int, input().split())
    dist = [[inf for _ in range(n + 1)] for _ in range(n + 1)]
    for _ in range(k):
        s, e = map(int, input().split())
        dist[s][e] = 1
    FloydWarshall()
    for _ in range(int(input())):
        s, e = map(int, input().split())
        if dist[s][e] != inf:
            print(-1)
        elif dist[e][s] != inf:
            print(1)
        else:
            print(0)