최소비용문제1 다익스트라 Djikstra 최단경로 알고리즘 (C++코드, Java코드) 다익스트라 알고리즘은 가장 기본적인 최단경로 알고리즘이다. 가장 기본적이란 말은 이외에도 벨만 포드, 플로이드 와샬 알고리즘이 있는데, 상대적으로 다익스트라가 대회에 많이 출제되기도 하고, 셋 중에 시간복잡도가 가장 빠른 알고리즘이기 때문에 꼭 숙지하는 것이 좋다. (참고로 시간복잡도는 각각 다익스트라 O(ElogV) / 벨만포드 O(VE) / 플로이드 와샬 O(V^3), 각각 사용되는 상황이 다름) 다익스트라 알고리즘은 한 정점에서 다른 모든 정점까지의 최소비용(최단거리)을 구하는 알고리즘이다. 내가 다익스트라를 사용하는 문제 유형은 다음과 같다. 1. 최단거리 / 최소비용 문제이다. 2. 문제를 읽었을 때, 문제의 의도가 한두 개의 적은 수의 출발점을 강조한다. (만약 모든 출발점이라면 플로이드와샬).. 2021. 5. 19. 이전 1 다음