최단경로 알고리즘 정리하다가 막혀서요. 다익스트라가 음수 가중치 간선 있으면 못 쓴다는 건 여기저기서 봤는데, 정작 왜 틀리는지 구체적인 반례로는 이해가 잘 안 돼요.


제가 생각한 그래프가 이런 건데요. 간선이 세 개예요.


A -> B : 1
A -> C : 5
C -> B : -4


여기서 A에서 B까지 진짜 최단은 A -> C -> B 해서 5 + (-4) = 1... 이 아니라 어라 이것도 1이네요. 값을 좀 바꿔서 A -> B를 3으로 하면 A -> C -> B가 1이라 더 짧고요.


제가 이해한 걸로는 다익스트라는 그리디라서 B를 한 번 확정하면 다시 안 건드린다는 가정으로 도는데, 이 가정이 음수 간선에선 깨진다는 거잖아요. 이 부분을 좀 명확하게 짚어주시고, 음수 있으면 벨만-포드 써야 한다는데 걔는 왜 되는지도 같이 설명해주시면 감사하겠습니다.