반응형
서론
다익스트라 알고리즘에서 음의 간선이 안되는 이유가 궁금해졌다.
안된다고 하는것은 당연히 똑똑한 사람들이 이미 증명한 결과라 안되는것은 맞지만
보다 보면 왠지 될것같기도 하다.
음의 간선일 때 다익스트라 알고리즘을 사용할 수 있는 경우를 들어봐도 글이라서 쉽게 와닿지 않았다.
역시 백문이 불여일견인 것 같다.
1. 음의 간선이 안되는 경우
다음과 같은 경우에 다익스트라 알고리즘은 A->B->D 총 비용 22가 가장 최소 경로라고 생각 할 것이다.
하지만 A->B->C->D가 총-90 으로 값이 더 작다.
그러면 모든 간선에 200을 더해줘서 음수를 없애면 되지 않을까?
2. 어떤 값을 더해서 다 양수로 만들어도 안되는 경우
안된다.
위의 그림에서 모든 간선에 200을 더해서 음수를 없앴지만
A->B->D가 가장 비용이 작은 경로가 되어버린다.
번외
그래프 그려주는 사이트 : https://csacademy.com/app/graph_editor/
