'플로이드 워셜' 태그의 글 목록

다익스트라, 벨만포드, 플로이드 워셜 ... 다 최단거리를 구하는 대표적인 알고리즘이다. 하지만 '최단거리'를 구한다는 공통적인 목표가 있지만, 각자 서로 다른 특징이 있기에 여러 알고리즘이 나눈다. 1. 다익스트라 장점 : 양의 간선이 존재할때 빠르게 최단거리를 구할 수 있다. 단점 : 음의 간선이 존재할때는 최단거리를 보장할 수 없다. 2. 벨만포드 장점 : 음의 간선이 존재할때 최단거리를 구할 수 있다. 단점 : 음의폐로가 존재할 수 있다. / 시간이 오래걸린다. 3. 플로이드 워셜 장점 : 하나의 정점에서 시작하여 다른 정점의 최단거리를 구하는 것이 아닌, 모든 정점을 기준으로 각 정점에 최단거리를 구한다. 단점 : 시간이 오래 걸린다. 위처럼 장/단점이 존재하기에 여러 최단거리 알고리즘이 있는데..

카테고리 없음 2023. 4. 10. 16:47

이전 1 다음