프로그래밍을 일상 생활속으로

  이전 글 참조 Dijkstra 알고리즘을 이용하여 출발점에서 종료점까지 가는 최소 비용의 경로를 찾을 수 있습니다. 하지만 시간 복잡도는 $$O(n^2)$$로 좋지 않습니다. Dijkstra 알고리즘은 종료점까지 도착한 경로들을 구한 뒤 가장 적은 비용의 경로를 선택합니다. 만일 각 노드마다 비용을 확인하여 도중에 탐색을 멈추게할 수 있다면 알고리즘을 개선할 수 있습니다.