jsjsjs0775   1년 전

아래 코드에서 42줄에 if (dist[from] != INF)를 빼주었더니 정답처리가 됐는데, 이게 INF 조건이 없어야 맞는 이유가 뭔지 모르겠네요..

xkdlaldfjtnl   1년 전

저 일단 906bc님의 조언을 토대로 알려드리면 


일단 벨만포드 알고리즘이 출발점이 특정한 한 점일때 가능한 알고리즘입니다. 

위의 코드의 경우 출발점이 1인 경우입니다. 


이럴때, dist[from]이 INF라서 지나치게 되면 , 뒤에 있는 cycle의 유무를 판단할 수 없게 되죠. 

만약 단절이 된 경우라면 dist[from]은 INF일테고, 단절된 정점끼리 cycle을 형성했다면? cycle은 형성되었지만, 문제에서의 cycle 유무는 알수가없어요. 

만약 

세 정점 1, 2, 3 이고, 간선이 두 개 

2 3 -1

3 2 -1 

인 경우에요 

그래서 방법은 두가지가 있다고 생각해요. 

1. 모든 정점을 출발점으로 조사해서 cycle의 유무를 파악하는 방법. 

2. 이 알고리즘에서 cycle의 형성 유무에 대해서 잘 생각해보기

2의 방법은 벨만포드 알고리즘에서 사이클의 형성이 언제 어떻게 되는지 알면 쉽게 이해하실 수 있을거에요 

INF의 값을 설정하는 이유는 단절이 되었다를 표시하고, 어떤 지점으로 부터의 거리를 구하려고 할 때 쓰입니다. 왜냐면 단절된 경우에는 갈 수 없거든요. 

따라서 만약 단순 그래프에서의 사이클 유무만 파악할 때는 dist[]초기화를 어떤 값으로 해주어도 상관이 없어요. 왜냐면 거리를 구하는 게 아니라 마지막에서 음의 사이클이 존재할 때, 변화만 파악하는 것이니깐요. 

그래서 dist[]를 memset -1로 초기화 한 코드도 잘 통과했고요. 답변이 되었으면 좋겠습니다. 

xkdlaldfjtnl   1년 전

반례 추가합니다.

1
3 2 0
2 3 -1
3 2 -1

lys312510   11달 전

입력되는 시간값은  0 또는 양수입니다

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