[질문] 다익스트라나 벨만포드 배울때 항상 나오는말이

[ㅁㄴㅇ(211.59)]

음의 사이클이 있으면 작동하지 않는다 <-이건데

근데 음의사이클이 있으면

다익스트라나 벨만포드알고리즘이 무능해서 그런게 아니라

원래 최단거리라는게 존재할수 없지않음? 

[메리체리(mrscherry)]

맞음

[메리체리(mrscherry)]

근데 음의 사이클이 있으면 작동하지 않는다고 말하는 사람이 있음?

[시아닌(kimjg1119)]

당연하지

[시아닌(kimjg1119)]

벨만포드는 그냥 음사이클 검출이 될 뿐임

[하루룽(ailedear)]

ㅇㅇ 음의사이클에 포함되면 최단경로가 정의안되겠지

[하루룽(ailedear)]

반면 음의사이클이 있어도 그 사이클과 관련없는 경로는 최단경로 재댜로나옴

[ㅁㄴㅇ(211.59)]

아 정확히 정의하자면 1.무한루프돌거나(다익스트라) 2. 작동은 되는데 쓸모없는값이 나온다(벨만포드) 인듯