dijkstra1 [Algorithm] 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘 다익스트라 알고리즘은 1959년 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라가 개발한 최단 경로 탐색 알고리즘이다. 이 알고리즘은 그래프에서 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 데 사용되며, 실 생활에 사용되는 예시로는 최단 거리 알고리즘답게 내비게이션 시스템, 네트워크 라우팅 등과 같은 곳에 사용된다. 위 예제는 1번 노드(a)에서 5번 노드(b)로 가는 최단 거리를 구하는 과정을 나타낸 것이다. 기준이 되는 노드에서 방문하지 않은 각 노드 간의 거리를 계산하고, 이를 통하여 가장 낮은 거리로 계산되는 각 노도의 경로를 모두 계산하게 되는 것이다. 예제 아래는 heapq를 활용하여, 위의 예제를 다익스트라 알고리즘을 코드로 구현한 것이다. import hea.. 2024. 11. 27. 이전 1 다음
