플로이드 와샬

woohobi·2021년 9월 2일
0

알고리즘

목록 보기
3/5

플로이드 와샬

내일이 벌써 학과 알고리즘 대회여서 잠시 우선순위가 밀렸던 알고리즘을 다시 보고 있으니 벌써 망각곡선이 도졌나보다.. 내 망각곡선은 남들보다 가파른듯..^

오늘 정리할 알고리즘은 플로이드 와샬 알고리즘이다. 플로이드 와샬 알고리즘은 3중 for문으로 구현하는 알고리즘으로 최단 경로 알고리즘 중 가장 구현하기 쉽지만 매우 큰 시간복잡도 때문에 n의 범위를 잘 확인하고, 모든 노드에서의 최단 경로를 구해야 할 때만 사용하는 게 좋다고 생각한다.

플로이드 와샬 알고리즘은 모든 정점간의 최단 알고리즘을 단 한번의 시행으로 구할 수 있다.

음수 사이클이 아닌 음수 간선도 해당 알고리즘으로 값을 구할 수 있다.
a를 출발지, b를 도착지라고 하였을 때, k 정점을 경유하여 가는 길과 비교하여 구할 수 있다. 따라서 a,b,k에 대해 각각의 반복문을 돌려야 해서 3중 for문 O(n^3) 만큼의 시간 복잡도가 소요된다.

graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b]

예시 문제

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

import sys
n=int(input())
m=int(input())
INF=int(1e9)
graph=[[INF]*(n+1) for _ in range(n+1)]

for a in range(1,n+1):
    graph[a][a]=0

for _ in range(m):
    a,b,c= map(int, sys.stdin.readline().split())
    graph[a][b]=min(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 i in range(1,n+1):
    for j in range(1,n+1):
        print(0 if graph[i][j]==INF else graph[i][j], end=" ")
    print()

위의 코드에서 알 수 있다시피, graph를 INF(매우 큰 숫자로) 초기화 해준 뒤, for 문 에서 비교를 통해 더 작은 값으로 갱신시켜주면 마지막에 모든 노드에서의 최단 경로를 보장한다.

한 문제를 더 살펴보자
https://www.acmicpc.net/problem/10159

import sys

n=int(input())
m= int(input())
INF=int(1e9)

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

for i in range(m):
    a, b= map(int, sys.stdin.readline().split())
    graph[a][b]=1
for i in range(1,n+1):
    graph[i][i]=1

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 i in range(1,n+1):
    answer=0
    for j in range(1,n+1):
        if graph[i][j]==INF and graph[j][i]==INF: answer+=1
    print(answer)

오늘 플로이드 와샬 알고리즘을 정리한 이유이다. 이 문제를 처음 본다면 최단 경로와 우선 순위간의 어떤 관계가 있는지 직관적으로 알아차리기가 쉽지가 않다.
우선 순위를 비교한다는 점에서 위상정렬이 떠오르지만, 플로이드 와샬을 통해 간단히 해결할 수 있다.

정점 간의 연결할 수단이 없다면 순위를 비교할 수 없다고 생각할 수 있고 graph[a][b], graph[b][a]가 모두 INF라면 둘은 우선순위를 비교할 수 없다.

profile
CDD - Coffee Driven Development

0개의 댓글