플로이드 워셜(Floyd-Warshall) 개념

목차

1. 개념

2. DP 점화식

3. 코드

 

 

1. 개념

플로이드 워셜 알고리즘이란 가중치 그래프에서 [ 모든 노드 > 모든 노드 ] 간의 최단 경로 길이를 구할 때 사용하는 알고리즘이다. 다익스트라와 벨만 포드 알고리즘이 [ 특정 노드 > 모든 노드 ] 최단 경로 길이를 구하는 것과 대비된다. 또한, 음수 가중치를 갖는 간선이나 음수 사이클이 없는 경우에만 사용될 수 있다. 이 조건은 다익스트라를 사용할 수 있는 조건과 동일하다. 

 

다익스트라 알고리즘이 그리디 방식의 알고리즘이었다면, 플로이드 워셜 알고리즘은 DP(동적 프로그래밍) 으로 최단 경로를 구하게 된다 이와 관련해서는 [ 2.DP 점화식 ]에서 살펴보자.

 

정리를 해보면 아래와 같다.

플로이드 워셜 알고리즘 
사용 조건
1. 음의 간선이 없는 가중치 그래프
2. [모든 정점 > 모든 정점] 으로의 최단 경로

구현 방식 - DP (동적프로그래밍)

 

 

2. DP 점화식

플로이드 워셜 알고리즘의 DP 아이디어를 알아보자.

 

아이디어

시작 노드 s, 거쳐가는 노드 k, 도착 노드 e 라고 할 때,

특정 노드k 에 대해, 아래 1, 2번을 비교해서 작은 값으로 s > e 로의 최단 경로를 갱신한다.

1. s > e 최단 경로

2. [ s > k 최단경로 ] + [ k > e 최단경로 ] 

 

거쳐 가는 노드 u 를 변경하여 

s > e 로 가는 최단 경로의 길이를 갱신해준다.

 

 

점화식 정의

dist[i][j] = [i 노드 > j 노드] 로의 최단 경로 길이

 

 

점화식 수식

dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

 

이전에 구했던  {  dist[ i ][ j ] } 와 { k 노드를 거쳐서 i > j 로 가는 최단 거리 } 중 최솟값을 dist[ i ][ j ] 로 갱신해준다. 

 

 

3. 코드

def floyd():

    # dist[i][j] = [i 노드 > j 노드] 로의 최단 경로 길이
    # 초기 무한대의 값으로 초기화 시킴
    dist=[[INF for _ in range(n+1)] for _ in range(n+1)]
	
    
    # 입력으로 간선의 길이가 주어질 시, 
    # 해당 간선이 초기 a > b로의 최단 거리가 되기 때문에 dist[a][b] = 간선의 길이 를 넣어준다.
    for _ in range(m):
        a,b,c,=map(int,input().split())
        adj[a][b]= c

    # 자기 자신으로의 최단 거리는 0 이므로 초기화
    for i in range(1,n+1):
        adj[i][i]=0


    # 경유 노드 = k, 시작 노드 = i, 끝 노드 = j
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
            
            	# [i 노드 > j 노드 최단 길이] vs [k 노드를 거쳐 가는 최단 길이] 
                adj[i][j]=min(adj[i][j],adj[i][k]+adj[k][j])

 

 

 

[참고 링크]

김종만 - 알고리즘 문제해결 전략

나동빈 - 이것이 취업을 위한 코딩테스트다