목록벨만포드 (1)

Game Develop

음수사이클이 있는 그래프 (다익스트라, 벨만포드, 플로이드와샬)

보통 음수가중치(가중치의 합이 음수값이 되는)를 갖는 간선이 있을 경우 다익스트라를 사용해도 되는 경우가 있고, 안되는 경우가 있다. 이 글에서의 다익스트라는 우선순위큐와 인접리스트를 사용한 다익스트라라고 가정한다. 아래의 그림을 봐보자. 시작은 s에서 시작한다고 가정한다. c와 d를 봐보자. c->d는 6이고 d->c는 -3이다. 이경우엔 음수간선이 있지만 음수사이클은 발생하지않는다. 먼저 c에대한 거리값은 5로 업데이트 될 것이다. 후에 c에서 d를 뽑아서 d에 대한 거리값을 11로 업데이트 후, d를 뽑았을 때 c로 가는 간선이 있기 때문에 c에대한 최솟값갱신을 시도해볼 것이다. 11-3을 하면 8인데, 이미 더 짧은 5로 저장되어있기 때문에 갱신될 일은 없고 여기서 그냥 끝이다. 이렇게 위와 같이..
Algorithm/Algorithm 2022. 12. 26. 01:56
이전 Prev 1 Next 다음