다익스트라 알고리즘 질문

[123(165.132)]

형님들 다익스트라 알고리즘에서

싸이클 있으면 왜 안되는 거에요?

[익명(220.118)]

그것이 아니라 음수 가중치에서 안돌아가는 겁니다. 음수 가중치를 갖고있는 선이 있으면 무한반복되겟죠?

[익명(220.118)]

아. 음수 싸이클이 있으면 안돌아가요

[ㅂㅂ(14.47)]

사이클이 아니더라도 음수가 있어선 무조건 안됌. 다익스트라는 정점을 거칠 때, 적어도 비용이 전보단 커진다는 전제가 있어야 최단비용을 정확히 구할 수 있음

[asd(104.10)]

굳이 음수 싸이클이 아니더라도 음수 가중치만 있어도 안돌아감

[asd(104.10)]

음수 가중치 있을때는 벨만포드 써야지 뭐

[익명(182.211)]

거에요->거예요 (받침 있으면 이에요 없으면 예요 이로 끝나면 받침 없으므로 예요 아니에요는 예외 인명엔 예요(예 : 길동이예요) 성까지 쓰면 이에요(예 : 홍길동이에요)) [리듬 맞춤법 봇♬]

[익명(182.211)]

ㅂㅂ//됌->됨 (되어 = 돼임) [리듬 맞춤법 봇♬]

[123(165.132)]

흠

[rayr(24.86)]

a->b->c->d->a로 이어지는 cycle에서 각각 1 2 4 -5의 weight을 가지고 있다고 가정할때, abcda cycle이 반복될수록 음수 가중치때문에 계속해서 비용이 적어짐. 결국엔 negative infinity까지 가게되고. 구글에 dijkstra's algorithm animation하면 쉽게 이해할듯