다익스트라1 최단 경로 찾기 : 다익스트라(Dijkstra) 알고리즘 들어가며 지난 포스트에서는 그래프를 탐색하는 두 가지 방법인 DFS와 BFS에 대해서 알아보았습니다. 이번에는 그래프 상의 최단 경로를 찾는 알고리즘 중 하나인 다익스트라(Dijkstra, 또는 데이크스트라) 알고리즘에 대해서 알아보겠습니다. 다익스트라 알고리즘은 1972년도에 튜링상을 수상했던 에츠허르 데이크스트라(Edsger Wybe Dijkstra)가 1956년에 고안한 알고리즘으로, 암스테르담에서 약혼녀와 쇼핑을 하다가 카페 테라스에서 잠깐 쉬어가던 중 "한 도시에서 다른 도시로 가는 가장 짧은 길이 무엇일까?" 를 생각하며 고안하게 되었다고 하네요. 이 알고리즘은 그래프 상의 최단 경로를 찾는 알고리즘으로, DFS나 BFS와 같이 정점과 간선으로 이루어진 구조에서 사용됩니다. 그 중에서도 간선의.. 2023. 4. 2. 이전 1 다음