벨만포드2

• 

  [c++] 백준-1865 웜홀 (벨만포드) 1. 문제 2. 입 출력 3. 예제 4. 문제 해설 벨만 포드 알고리즘을 이용해서 (음의 가중치가 있기 때문이다! 웜홀) 음의 사이클이 존재하는 지를 판단하면 되는 문제였다. 이 문제는 그러나 일반적인 벨만포드 알고리즘과는 다른 점이 두 가지가 존재한다. 웜홀이 아닌 도로의 경우 양방향 도로이다. 출발 노드가 정해져있지 않다. 벨만포드 알고리즘은 모든 간선을 노드 수 -1 만큼 탐색하면서 한 노드로부터 다른 노드들의 최단 거리를 갱신해가는 알고리즘이다. 원래는 간선의 시작 노드에 해당하는 노드를 방문한 적이 없다면 continue를 통해 넘기는 로직이 존재한다. 왜냐하면 시작 노드가 존재하기 때문에 시작노드로부터 간선이 도착한 적이 있어야 최단 경로를 계산할 수 있기 때문이다. 하지만 이 문제에서는 시작.. c++/알고리즘 2023. 2. 7.

• 

  [c++]벨만포드 알고리즘 - 백준 타임머신 11657 벨만포드 알고리즘이란? 벨만포드 알고리즘이란 음의 가중치가 존재할 때 최단 경로를 구하는 알고리즘이다. 양의 가중치만이 존재할 때 다익스트라 알고리즘을 이용해 최단 경로를 구한 것과는 다르게 벨만포드에는 음의 가중치가 존재한다. 다익스트라 알고리즘은 현재 선택한 것이 최선의 선택이라는 greedy알고리즘을 기반으로 한다. 하지만 음의 가중치가 존재한다면 음의 가중치를 여러번 지날 수록 최단 경로는 오히려 줄어들게 되는 경우가 존재한다. 따라서 greedy 알고리즘에 위배된다. 특징 음의 가중치를 가지는 간선도 가능하다. 음의 사이클의 존재 여부를 확인할 수 있다. 최단 거리를 구하기 위해서 v-1번 E개의 모든 간선을 확인한다.(다익스트라가 노드 중심의 알고리즘이라면 벨만포드는 간선 중심이다.) 총 연산.. c++/알고리즘 2023. 1. 26.