플로이드-워샬 알고리즘

플로이드-워샬 알고리즘

시간복잡도 O(N^3)

정점에서 다른 정점까지 최단거리를 구하는 알고리즘.

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

플로이드-워샬 알고리즘은 모든 정점을 다른정점과 최단거리를 구해주는 알고리즘이다.

 

방법

꼭지점 k를 중간 노드로 삼아서 모든 그래프가 k를 지나가는 방법과 바로가는 방법중 더 작은 값을 새로 등록한다.

 

위와같이 있을때 k가 3이라고 가정하면 1->4와 1->3->4로 나눠보고 더 작은값인 1->4의 4를 채택해서 새로 등록한다.

모든 k에 대해서 반복하고 모든 2차원 그래프를 탐색하니 O(N^3)의 시간복잡도가 된다.

 

 

 

코드

for k in range(N):
  for i in range(N):
    for j in range(N):
      arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j])

 

 

 

 

참고한 사이트

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

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

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

17182번: 우주 탐사선

이 문제로 처음 접했다.