플로이드 워셜 알고리즘

플로이드 워셜 알고리즘은 '모든 정점간에 최단거리를 구하는 알고리즘' 입니다.

시간 복잡도는 O(n^3)이다.

두개의 정점과 정점을 거치는 중간점 총 3개를 모두 탐색해야 합니다.

핵심은 거쳐가는 정점을 기준으로 최단거리를 알아내는 것입니다

다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로의 최단거리를 구하는 문제 입니다. 

 

다익스트라 알고리즘	플로이드 워셜 알고리즘
한 정점에서 다른 모든 정점으로의 최단 거리 구하는 알고리즘	모든 정점에서 모든 정점으로의 최단거리 구하는 문제

 

코드 먼저 살펴보겠습니다

v, e = map(int, input().split())

INF = 10000000
dist = [INF * (v+1) for _ in range(v+1)]

# 입력받은 간선들에 대한 정보로 거리정보 그래프를 업데이트 해줌

for k in range(1, v+1) :  
	for i in range(1, v+1) :  
    		for j in range(1, v+1) :   
        			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
            
print(dist)

 

기본 로직 설명

1. 모든 그래프를 무한대의 거리로 초기화 합니다
2. 입력 받은 정보들로 그래프를 업데이트 해줍니다.
3. 모든 정점들을 순회 합니다. 순회하는 대상 정점은 중간노드가 됩니다.
4. 현재 그래프의 값과 중간노드를 거쳐서 오는 거리를 비교하여 최솟값을 갱신해 줍니다. 

 

---

 

문제예시

 

아래는 백준에서 풀게된 플로이드 워셜 알고리즘을 이용한 문제입니다.

아래의 문제를 설명하면서 알고리즘을 같이 설명하겠습니다.

 

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

1956번: 운동

 

백준 문제

 

문제에서 주어진 예시 입력을 그래프로 표현한 이미지 입니다.

정점과 간선으로 표현한 그래프

 

 

위 테이블은 정점과 거리의 정보를 테이블로 표시한 것입니다.

이제 이 테이블을 기반으로 거리가 어떻게 업데이트가 되는지 살펴보겠습니다.

 

아래에 나올 테이블 이미지에서 색깔로 표시된 영역은 업데이트 대상 영역입니다.

표시되어 있지 않은 영역은 거쳐가는 정점이 속해 있기 때문에 업데이트를 하는 대상이 아닙니다

(ex. 1번 정점에서 1번 정점을 거쳐 3번 정점에 도착하는 것은 1번 정점에서 바로 3번 정점으로 가는것과 같습니다.

dist[1][1] + dist[1][3] : dist[1][3])

 

 

1. 1번 정점이 중간 노드가 되었을때

 

2. 2번 정점이 중간 노드가 되었을때

두개의 거리가 업데이트 되었습니다. ([1,3], [3,3])

직접 내용을 살펴보면

dist[1][2] + dist[2][3] : dist[1][3] == 3 : 5 (1번 정점을 지나온후의 그래프 기준)가 나왔기 때문에

1번 정점에서 3번 정점으로 가는 거리는 2번 정점을 거쳐가는것이 더 거리가 짧습니다.

[3,3]번도 마찬가지 입니다.

 

3. 3번 정점이 중간 노드가 되었을때

업데이트 되는 경우는 2번 노드에서 설명한 경우와 같습니다

 

문제에서는 자기 자신으로 돌아오는 사이클의 최단거리를 구하길 원했으므로 자신으로 돌아오는 간선들의 값만 비교하여 최솟값을 구하면 됩니다.

 

 

문제에 대한 정답 코드

import sys
v, e = map(int, input().split())
INF = 100000000
dist = [[INF] * (v + 1) for _ in range(v + 1)]

for _ in range(e) :
  start, end, distance = map(int, sys.stdin.readline().split())
  dist[start][end] = distance

for k in range(1, v + 1) :
  for i in range(1, v + 1) :
    for j in range(1, v + 1) :
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
  print(dist)

answer = INF
for i in range(1, v+1) :
  answer = min(answer, dist[i][i])

if answer == INF :
  print(-1)
else :
  print(answer)

 

 

 

 

출처: https://chanhuiseok.github.io/posts/algo-50/

알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘

https://blog.naver.com/ndb796/221234427842

24. 플로이드 와샬(Floyd Warshall) 알고리즘