728x90 힙구조1 다익스트라 알고리즘(Dijkstra Algorithm) 안녕하세요. 옆집 컴공생입니다. 오늘은 다익스트라 알고리즘을 배워볼거예요. 다익스트라(Dijkstra Algorith)은 다이나믹 프로그래밍을 활용한 대표적인 최단경로(Shortest Path) 탐색 알고리즘입니다. 흔히 인공위성 GPS 소프트웨어등에 많이 이용된다고 하네요. 음의 간선을 포함할 수 없는데 현실에는 음의 간선이란 게 존재하지 않잖아요? 그러니깐 매우 현실적인 알고리즘 중 하나라고 할 수 있겠습니다. 다익스트라 알고리즘은 다이나믹 프로그래밍이나 그리디 알고리즘을 분류가 되는데요. 다이나믹 프로그래밍인 이유는 이러합니다. '최단거리는 여러 개의 최단거리로 이루어져 있다.' 너무 당연하게도, A -> B -> C -> D 로 가는 최단 걸이로 가는데 A -> C -> B 가 A -> B -> .. 2020. 6. 10. 이전 1 다음 728x90
