목록플로이드 와샬 C# (1)

YJ_Scribbles

동적계획 알고리즘 _플로이드 와샬 알고리즘

ㅇ 다익스트라(Dijkstra)의 최단 경로 알고리즘 이용 - 각 점을 시작점으로 정하여 다익스트라 알고리즘 수행 - 시간복잡도 : n x O(n²) = O(n³) (단, n은 점의 수) ★ 플로이드 와샬 알고리즘 -> 모든 쌍의 최단경로(All Pairs Shortest Paths)문제 -> 여러지점에서 각각의 최단 경로를 구하는 문제 - Warshall은 그래프에서 모든 쌍의 경로 존재 여부를 찾아내는 동적 계획 알고리즘을 제안 - Floyd는 이를 변형하여 모든 쌍 최단 경로를 찾는 알고리즘을 고안 -> 모든 쌍 최단 경로를 찾는 동적 계획 알고리즘 : 플로이드-워샬 알고리즘 (간단히 플로이드 알고리즘) - 플로이드 알고리즘의 시간복잡도 : O(n³) (다익스트라 알고리즘을 n번 사용할 때의 시간복..
이론_전공/알고리즘 2020. 12. 1. 03:21
이전 Prev 1 Next 다음