*참고 - 나동빈 유튜브 https://gae-gi-da.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Dijkstra 알고리즘 - 다익스트라 알고리즘(Dijkstra) *참고 저서 나동빈 저 최단 경로 문제 유형에서 가장 많이 사용되는 알고리즘 중 하나로, 특정 노드에 대해 각 노드들까지의 최단 경로를 구하는 알고리즘이 gae-gi-da.tistory.com 다익스트라 알고리즘은 이전 포스트에서 말했듯이, 모든 간선의 가중치가 양수일 때만 적용이 가능하다. 현실의 상황에서는 간선의 가중치, 즉 거리가 음의 ..