[백준 파이썬 11404번 플로이드] 플로이드 워셜 알고리즘

다익스트라로 풀었다가 시간초과가 났다

 

플로이드 워셜 알고리즘

‘거쳐가는 정점’을 기준으로 최단 거리를 구하는 알고리즘

 

장점

벨만-포드와 같이 음수 가중치가 있어서 가능하다 (단, 똑같이 음수 사이클이 있으면 안됨)

방향, 무방향 그래프 모두 가능하다

모든 쌍의 최단 거리를 구할 수 있다

 

단점

시간복잡도가 O(n**3)이다…

심지어 중간 결과를 저장하려면 많은 양의 메모리를 필요로 한다.

 

플로이드 워셜 vs 다익스트라

플로이드 와셜은 모든 거리를 구해야할 때 다익스트라보다 효과적이다

다익스트라는 각 시작노드마다 한번씩 돌려야 하기 때문 + 같은 노선의 버스가 여러대 있기 때문

 

+ 참고

• 플로이드 와셜의 시간복잡도 : O(V^3)
• 다익스트라의 시간복잡도 : O((V + E) log V)

 

 

예제 문제

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

11404번: 플로이드

다익스트라 풀이 - 시간초과

import sys
import heapq

input = sys.stdin.readline
N = int(input())
M = int(input())

route = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b, c = map(int, input().split())
    route[a].append([b, c])

def dijk(start):
    INF = int(1e9)
    result = [INF for _ in range(N + 1)]
    result[start] = 0

    q = []
    heapq.heappush(q, (0, start))

    while q:
        cdist, cnode = heapq.heappop(q)
        for nnode, ndist in route[cnode]:
            cost = ndist + cdist
            if cost < result[nnode]:
                heapq.heappush(q, (cost, nnode))
                result[nnode] = cost

    return result[1:]

for i in range(1, N + 1):
    for a in dijk(i):
        print(a, end=" ")
    print()

 

플로이드 와셜 정답풀이

import sys

input = sys.stdin.readline
N = int(input())
M = int(input())

INF = int(1e9)
cost = [[INF for _ in range(N + 1)] for _ in range(N + 1)]
for i in range(1, N+1):
    cost[i][i] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    cost[a][b] = min(cost[a][b], c)

for k in range(1, N+1):
    for a in range(1, N+1):
        for b in range(1, N+1):
            if a == b :
                cost[a][b] = 0
            else:
                cost[a][b] = min(cost[a][b], cost[a][k] + cost[k][b])

for i in range(1, N+1):
    for j in range(1, N+1):
        if cost[i][j] == INF:
            cost[i][j] = 0
        print(cost[i][j], end=" ")
    print()