홍시홍의 프로그래밍

[알고리즘] 플로이드 워셜(시간 복잡도, 사용하는 곳, 특징, 구현방법) 본문

알고리즘

[알고리즘] 플로이드 워셜(시간 복잡도, 사용하는 곳, 특징, 구현방법)

홍시홍 2020. 6. 11. 12:26

시간 복잡도

모든 정점에 대해서 모든 가능성을 검사한다

O(V^3)

 

사용하는 곳

모든 최단 경로를 알고 싶을 경우

 

특징

음의 가중치가 있어도 사용 가능하다

 

구현방법

거리가 업데이트될 수 있으면 계속해서 업데이트 해준다

 

아래 블로그에 자세히 설명되어 있다

https://hsp1116.tistory.com/45

 

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

앞서 다익스트라 알고리즘 포스트에서, 그래프에서 정점끼리의 최단 경로를 구하는 문제는 여러가지 방법이 있다고 했다. 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제(si

hsp1116.tistory.com

 

'알고리즘' 카테고리의 다른 글

[알고리즘] dfs(깊이 우선 탐색, 시간 복잡도, 사용하는 곳, 특징, 구현방법)  (0) 2020.08.31
[알고리즘] 벨만포드 (특징, 시간복잡도, 구현 방법)  (0) 2020.06.11
[알고리즘] 프림 알고리즘(시간 복잡도, 구현방법, 특징)  (0) 2020.06.11
코사라주 알고리즘(시간복잡도, 구현 방법, 준비 사항)  (0) 2020.06.10
위상 정렬(사용하는 이유, 특징, 구현, 시간 복잡도)  (0) 2020.06.10
'알고리즘' Related Articles more
Comments