컴공생의 다이어리

다익스트라(Dijkstra) 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘 특정한 노드에서 출발해 연결되어 있는 다른 모든 노드로 가는 최단 경로를 구하기 위한 알고리즘 0보다 작은 값을 가지는 음의 간선이 없어야 정상적으로 동작 보통 우선 순위 큐를 구현하기 위해 사용되는 heapq 라이브러리를 활용해서 구현 GPS 소프트웨어의 기본 알고리즘으로 채택 과정 출발 노드를 설정 출발 노드를 기준으로 각 노드의 최소 비용을 저장 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신 위의 3번 ~ 4번 과정을 반복 동작 단계에 대한 예시는 아래 게시물이 잘 정리되어 있으니 참고하면 좋을 것 같다! [알고리즘] 다익스트..