플로이드 워셜 알고리즘

2021 카카오 신입공채 1차 온라인 테스트의 4번, 택시 합승 문제 풀이법 중 하나.
문제 바로가기
나무위키 참고

그래프에서 가능한 모든 노드 쌍에 대한 최단 거리를 구하는 알고리즘. 시간복잡도는 O(n^3)

백준-플로이드

# 11404 boj

# n ㄱㅐ의 도시,
# m 개의 버스
# 모든 도시 쌍 a,b 에 대하여, a-b 로 가는 데에 필요한 비용의 최솟값

# 도시 개수
n = int(input())
# 버스 개수
m = int(input())
# 버스 정보
bus = [list(map(int, input().split())) for _ in range(m)]

city = [[0 for _ in range(n)] for _ in range(n)]

for start, end , cost in bus:
    if city[start-1][end-1] == 0 or city[start-1][end-1] > cost:
        city[start-1][end-1] = cost


for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:
                city[i][j] = 0
            elif city[i][k] != 0 and city[k][j] != 0 and (city[i][j] == 0 or city[i][j] > city[i][k] + city[k][j]):
                city[i][j] = city[i][k] + city[k][j]

for i in city:
    i = list(map(str, i))
    print(' '.join(i))