john6014   4년 전

mcmf 문제풀다보면 가중치가 음수가 나와서 주로 벨만포드나 spfa로 문제를 해결한다고 배웟습니다

spfa 가 조금 더편하다고 느껴서 항상 spfa 로만 풀다가 이번에 벨만포드로 푸는 방법을 배우는중인데

벨만포드는 음수사이클을 확인하기 위해 한단계 더 돌려서 최단 값이 바뀌면 음수사이클이 존재한다 이런식으로 판별하는데

mcmf 문제에서는 그런식으로 푸는 분이 없으시더라구요

그냥 문제자체가 음수사이클을 확인할필요가 없어서 배제하신건지 아니면 원래 mcmf 에서는 할필요가 없는것인지 알려주시면 감사하겠습니다.

startlink   4년 전

처음 만든 그래프에 음수 사이클이 없으면, MCMF를 돌리는 중에도 음수 사이클이 나타나지 않습니다.

댓글을 작성하려면 로그인해야 합니다.