목록2024/09/21 (1)
미소를뿌리는감자의 코딩
[~ to Many] Dijkstra Algorithm & Floyd Warshall Algorithm
1. 개요Dijkstra Algorithm과 Floyd Warshall Algorithm을 이용하는 이유가 무엇일까? MST의 kruskal Algo. 와 Prim. Algo 와는 다른 점이 무엇일까?MST의 경우엔, 모든 vertex를 방문할 수 있는 최단 경로를 나타낸다. 반면 Dijkstra는 하나의 vertex에서 다른 vertex까지의 최단 경로를 나타낸다.Floyd Warshll은 한 vertex에서 다른 vertex까지의 모든 최단 경로를 알아내고자 사용하는 알고리즘이다. 따라서, Dijkstra는 O(n^2)의 시간 복잡도를, Floyd Warshall은 O(n^3)의 시간 복잡도를 가진다. 아래 코드에서 Floyd Warshall 알고리즘을 Bellman Ford 알고리즘으로 잘못 적었다..
코딩 이야기
2024. 9. 21. 13:16