Bellman-ford2 [BOJ] 백준 1865 - 웜홀 문제 링크 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 지점(정점), 도로(무방향 간선), 웜홀(음의 가중치를 갖는 유방향 간선)으로 이루어진 그래프에서 출발을 하였을때보다 시간이 되돌아가 있는 경우(음의 사이클)가 존재하는지 찾는 문제이다. Bellman-Ford 알고리즘으로 해결할 수 있었다. 해당 알고리즘은 아래 링크에서 확인 할 수 있다. 2021.04.06 - [Algorithm/Theory] - [Algorithm] Bellman-Ford Algorithm (벨만-포드 알고리즘) [.. 2021. 4. 6. [Algorithm] Bellman-Ford Algorithm (벨만-포드 알고리즘) Bellman-Ford 알고리즘은 Dijkstra 알고리즘과 마찬가지로 단일 정점에서 각 정점까지의 최단거리를 구하는 알고리즘이다. 시작점은 1번 정점이다. dist배열은 시작점으로부터의 거리를 나타내고 INF로 초기화 되어있다. 초기상태는 아래와 같으며 그래프의 구현은 인접 행렬(Adjacency Matrix) W로 되어있다. 시작점이 1번 정점이기 때문에 dist[1]을 0으로 갱신한다. 한 정점과 인접한 정점을 중심으로 갱신을 이어나간 Dijkstra 알고리즘과는 달리 Bellman-Ford 알고리즘은 매 수행마다 모든 간선(edge)에 대해 갱신을 진행한다. 한 간선이 정점 i에서 정점 j로 이어진다고 할 때, 다음 연산을 통해 갱신이 진행된다. dist[j]=min(dist[j],dist[i]+.. 2021. 4. 6. 이전 1 다음
