[항해99] 최단경로 찾기 - 플로이드

플로이드?

다익스트라 알고리즘이 한 정점에서 다른 정점까지의 최단거리를 구하는 알고리즘이라면,

플로이드는 어떤 정점에서 다른 정점까지의 최단거리를 모두 구하는 알고리즘이다.

 

코드로 보도록 하자.

INF = int(1e9)


n = int(input())
m = int(input())

graph = [[INF] * (n+1) for i in range(n+1)]

# 자기 자신으로 가는 노드는 거리가 0 이라고 가정
for i in range(1,n+1):
    graph[i][i] = 0

# 그래프 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    if c < graph[a][b]:
        graph[a][b] = c

# 거리의 최솟값 구하기
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 그래프 출력
for row in graph[1:]:
    print(" ".join([str(el) if el != INF else '0' for el in row[1:]]))

 

그래프에 거리를 저장하는데, a에서 b를 바로 가는 거리보다 k를 거쳐가는 거리가 더 짧으면, a에서 b로 가는 거리를 갱신해준다. 

백준 1753 최단경로

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

1753번: 최단경로

플로이드 알고리즘으로 풀어도 되지만, 메모리 부족으로 오답처리 되니, 다익스트라 ( 힙을 이용해서)로 풀면 정답처리 되는 것을 볼 수 있다. 

import heapq
INF = int(1e9)


# N is the number of Nodes, M is the number of Edges
# N starts at 1
N, M = map(int, input().split())
start = int(input())

graph = [[] for i in range(N + 1)]
dist = [INF] * (N + 1)

for i in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

def dijkstra_pq(start):
    q = []
    heapq.heappush(q, (0, start))
    dist[start] = 0

    while q:
        acc, cur = heapq.heappop(q)

        if dist[cur] < acc:
            continue

        for adj, d in graph[cur]:
            cost = acc + d
            if cost < dist[adj]:
                dist[adj] = cost
                heapq.heappush(q, (cost, adj))

    for d in dist[1:]:
        if d == INF:
            print("INF")
        else:
            print(d)


dijkstra_pq(start)

백준 1956 운동

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

1956번: 운동

플로이드 알고리즘이용해 모든 거리를 구한다. 자기 자신으로 가는 거리를 초기화 할 때 0이 아니라 INF 로 초기화되고, 맨 마지막에 graph[i][i]를 모아놓으면 자기 자신으로 가는 거리가 나오는데, 이 중에서 가장 작은 값을 출력하면 된다.

 

근데 만약에 가장 작은 값이 1e9라면 ( INF라면 ) "INF"를 출력하도록 해야한다.

 

회고

최단거리 알고리즘은 오늘 문제 풀면서 어느정도 더 익숙해진 것 같다. 

 

처음 항해에 들어왔을 때와 비교해서 마음이 좀 풀린 것 같다. 늘 겸손하게 꾸준함을 가지고 노력하자.