[질문] SPFA질문점

[pspspsp..(219.248)]

이 코드 보고있는데 음의 사이클이 있으면 계속 돌아가는거 아님? 예를 들면 1 -> 2 -> 3 -> 1 로 음의 간선으로 연결되어있으면 무한히 갱신되면서 큐에 계속 들어갈거같은데

- dc official App

[Rustie(sanholobeats)]

그래서 한 정점을 n번이상 방문했는지가 음수사이클의 존재성임

[EN_SA(encludingsalt)]

저대로 구현하면 무한루프빠지는거 맞을듯

[ㅁ(141.223)]

애초에 음수 사이클 있으면 벨만포드도 무한루프 생김. SPFA만이 아니고 음수간선있는 최단거리 문제는 다 그럼. 하지만 SPFA를 쓸때는 flow graph에서 사용할텐데, 여기서는 flow를 정상적으로 흘려줬다면 첫 그래프에서 음수 사이클이 없다->나중에도 음수 사이클 안생긴다가 증명되서 걍 써도됨

[pspsps(182.231)]

걍 플로우 최대량이 정해져 있어서 무한루프 빠질 걱정 없다 이렇게 이해하면 됨?

[ㅁ(119.202)]

ㄴ

[pspspsps(219.248)]

그럼 애초에 시작할때 비용에 대해 음의 사이클이 있으면 안돌아가나요? - dc App

[ㅁ(119.202)]

ㅇㅇ 플로우 1만 흘려준다고 해도 음의 cost를 가지는 cycle있으면 그냥 안돌아감. 그경우는 MCMF문제가 아니거나 그래프를 잘못 설계한거임. 나중에도 음수 cycle이 안생긴다는건 귀납법으로 간단히 증명 가능함

[pspspsps(182.231)]

왜 음의사이클이 애초에 존재하면 안돌아가죠? 플로우 양이 정해져있어서 플로우때메 안돌아가게되지 않음? - dc App