[BOJ] 플로이드 (G4, 11404) : 플로이드-워셜 vs 다익스트라

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

 

 

이 문제를 다익스트라, 플로이드-워셜 둘 다 써서 풀어보았습니다.

 

(1) 다익스트라

- 하나의 시작점에서 각 점들까지의 최단 경로를 계산합니다.
- heap 기반 알고리즘으로 최단 비용을 차례 차례 뽑아나가는 방식입니다.
- 그리디 알고리즘 기반이며, 음수 가중치가 포함될 경우 다른 방법을 써야 합니다.
- 시간 복잡도 : ElogV

# solution (1) dijkstra로 풀어 보기. 하나의 점에서 거리 구하기.
# Time complexity: VlogE
# 특징점 : 음의 가치에서는 사용 불가!

import sys
import heapq
input = sys.stdin.readline

INF = 1e12
vertex = int(input())
edge = int(input())
vertex_list = [[] for _ in range (vertex + 1)]


for _ in range(edge):
    start, end, cost = map(int, input().split())
    vertex_list[start].append((end, cost))

# 그리디 알고리즘, 가장 최저 비용 선을 추가한다.
def dijkstra(start, cost_list):
    q = []
    heapq.heapify(q)
    
    heapq.heappush(q, (0, start)) # cost, 시작점
    
    while q:
        cur_cost, cur_v = heapq.heappop(q)
        
        # 방문 처리임 이미 비용을 처리한 꼭지점인데... 더 크다면... 굳이?
        if cur_cost > cost_list[cur_v]:
            continue
        
        for next_v, next_cost in vertex_list[cur_v]:
            new_cost = cur_cost + next_cost
            # 더 적은 비용일때만 갱신하고, 그 점을 넣어
            if new_cost < cost_list[next_v]:
                cost_list[next_v] = new_cost
                heapq.heappush(q, (new_cost, next_v))
    return cost_list

for i in range(1, vertex + 1):
    cost_list = [INF] * (vertex + 1)
    cost_list[i] = 0
    cost_list = dijkstra(i, cost_list)[1:]
    for i in range(len(cost_list)):
        if cost_list[i] == INF:
            cost_list[i] = 0
        print(cost_list[i], end = ' ')
    print()

 

(2) 플로이드-워셜
- 모든 노드에서 다른 노드로 가는 최단 경로를 한 번에 계산합니다.
- DP 기반 알고리즘 입니다.  a->b가 가까운지, 어딜 거쳐 가는게 더 가까운지 이걸 계속 업데이트 합니다.
- 시간복잡도 : V^3
- DP 기반이기 때문에, 음의 가중치를 가져도 최단 거리 계산에 문제가 없습니다!!!!

# solution (2) 플로이드 워셜 알고리즘(Floyd-Warshall)로 풀어보기.
# 댜익스트라와의 차이점 : 모든 노드에서 다른 모든 노드 까지의 최단 경로를 한번에 모두 계산한다.
# 다익스트라는 그리디, 플로이드 워셜 알고리즘은 DP
# 기본 : Dab = in(Dab, Dak + Dkb)
# Time complexity : V^3
# 특징점 : 음의 가치를 가져도! 플로이드 워셜은 쓸 수 있다!, 한번에 모두 구한다!

import sys
input = sys.stdin.readline
vertex = int(input())
edge = int(input())
INF = 1e12
graph = [[INF for _ in range(vertex + 1)] for _ in range(vertex + 1)]

# step 1. 자기 자신으로 가는 비용은 0으로 초기화 해야함
for a in range(1, vertex+1):
    graph[a][a] = 0

# step 2. a에서 b로 가는 cost를 계산할 거임. row가  출발점, col이 도착점 기준이 된다.
# 이렇게 넣으면, 선이 없는 부분은 inf가 된다.
for _ in range(edge):
    start, end, cost = map(int, input().split())
    # 주의사항, 최소값이 아닐 수도 있어서 최소값 갱신 필요
    graph[start][end] = min(cost, graph[start][end])

# k를 거쳐 가면 더 최저가 될까? 를 dp로 풀기.
for k in range(1, vertex+1):
    for start in range(1, vertex+1):
        for end in range(1, vertex+1):
            graph[start][end] = min(graph[start][end], graph[start][k] + graph[k][end])

# 최종 출력 파트
for a in range(1, vertex+1):
    for b in range(1, vertex+1):
        if graph[a][b] == INF:
            print(0, end = ' ')
        else:
            print(graph[a][b], end = ' ')
    print()