최단 경로 (플로이드-와샬(Floyd-Warshall))

목차

다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘은 모두 그래프에서 최단 경로를 찾는 알고리즘입니다. 각 알고리즘은 특정한 조건에서 사용됩니다.
다익스트라 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 없는 경우)
벨만-포드 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 존재하는 경우. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능)
플로이드-와샬 : 모든 노드쌍에 대한 최단경로를 모두 찾을 때(음의 가중치가 없어도 있어도 모두 사용가능. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능)

플로이드-와샬(Floyd-Warshall)

• 플로이드-와샬 알고리즘은 모든 정점 간의 최단 경로를 찾는 알고리즘입니다.
  • 다익스트라나 벨만포드의 경우는 하나의 시작 정점에 대해 다른 정점들에 대한 최단 경로를 찾는 것입니다.
• 음의 가중치를 가지더라도 사용할 수 있습니다.
  • 플로이드-와샬 알고리즘 수행후 대각선 요소 중에서 0보다 작은 값이 있으면 그래프에 음의 사이클이 존재하는 것으로 간주할 수 있습니다. 대각선 요소가 자기 자신으로 가는 최단 경로의 가중치를 나타내기 때문에, 정상적인 경우에는 0이어야 합니다. 따라서 0보다 작다는 것은 자기 자신으로 돌아오는 경로 중 음의 가중치 사이클이 존재한다는 의미입니다.
• 플로이드-와샬(Floyd-Warshall)
  • 초기 설정 : 거래 행렬을 초기화합니다.(정점 i에서 정점 j로의 직접적인 간선이 있으면 그 가중치로 설정하고, 없으면 무한대로 설정합니다. (단, i=j인 경우 0으로 설정합니다.)
  • 업데이트 : 모든 정점 k에 대해 다음을 수행합니다. (i에서 j로 가는데 k를 거쳐가는 경우를 생각하는 것입니다.)
    • 모든 정점 i, j에 대해, distance[i][j] > distance[i][k] + distance[k][j] 이면 distance[i][j]를 distance[i][k] + distance[k][j]로 갱신합니다.
  • 시간복잡도는 O(V^3)입니다. (k,i,j 모두 정점의 개수만큼 진행되기 때문입니다.)

예시

• 백준 11404 플로이드 문제를 살펴보겠습니다.
• 모든 도시의 쌍 (A,B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하라고 하였습니다. 따라서 모든 정점 간의 최단 경로를 찾는 문제이기 때문에 플로이드-와샬 알고리즘으로 해결하면 됩니다.
• 코드

  • n = int(input())
    m = int(input())
    
    graph = [[] for _ in range(n+1)]
    
    inf = int(1e9)
    distance = [[inf for _ in range(n+1)] for _ in range(n+1)]
    
    for i in range(1,n+1):
        distance[i][i]=0
        
    for _ in range(m):
        s,e,w = map(int,input().split())
        distance[s][e]=min(distance[s][e],w)
    
    
    
    for k in range(1,n+1): # k를 거쳐가는경우를 하나씩 업데이트, 점점 업데이트 되면서i->j 속에는 최단거리로 이동하는 방법이 내재되어 있게됨.
        for i in range(1,n+1):
            for j in range(1,n+1):
                distance[i][j]=min(distance[i][j],distance[i][k]+distance[k][j])
    
    for i in range(1,n+1):
        for j in range(1,n+1):
            if distance[i][j]==inf:
                print(0,end=' ')
            else:
                print(distance[i][j],end=' ')
        print()