오구의코딩모험

오늘부터삼성 B형 시험 준비를 위해 자주 나오는 알고리즘을 하나씩 공부하려고 한다.기존에 공부했던 알고리즘도 있지만오랜만에 다시 살펴보니 기억이 가물한 알고리즘들이 많아서... 오늘은다익스트라 알고리즘부터 다시 공부하고자 한다. 플로이드-워셜 알고리즘 → 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘, O(n^3)다익스트라 알고리즘 → 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 , O(ElogV) 플로이드보다 다익스트라가 효율이 좋다. 하지만!!다익스트라는 음수 간선이 있을 경우 사용불가,플로이드는 음수 간선이 있는건 상관없으나 음수 사이클이 있을 경우 사용불가하다. 음수인 간선이 있는데 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하고싶다면?→ 벨만포드..