Final Challenge #1
Coddy의 벨만-포드 알고리즘 - 그래프 알고리즘 코스 레슨 — 9개 중 8번째.
챌린지
중급벨만-포드(Bellman-Ford) 알고리즘의 강력한 특징은 음수 사이클을 찾아내는 것입니다.
n과 평면화된 edges 배열(방향성이 있는 세 개의 값으로 구성된 튜플들)을 인자로 받아, 그래프에 음수 가중치 사이클이 포함되어 있으면 1을, 그렇지 않으면 0을 반환하는 hasNegativeCycle 함수를 작성하세요.
힌트: 모든 거리를 0으로 시작하고, 모든 간선을 n - 1번 완화(relax)한 다음, 한 번 더 확인하세요. 만약 여전히 완화될 수 있는 간선이 있다면, 음수 사이클이 존재하는 것입니다.
직접 해보기
#include <stdlib.h>
int hasNegativeCycle(int n, int* edges, int edges_size) {
// 여기에 코드를 작성하세요
return -1;
}
