음수가중치가 있는 그래프에서의 최단경로

[익명(175.223)]

음수 사이클이 없을 경우 대표적으로 벨만포드 알고리즘을 사용하던데

그냥 가장 작은 음수 가중치의 절대값을 모든 노드에 더해준 뒤에(최고 작은 가중치가 0으로 노말라이즈) 다익스트라로 해결하면 문제가 생길까요?

[익명(223.39)]

그렇게하면 지나온 경로 수가 상태에 들어가서 시간이랑 메모리 좆된다고 국비선생님한테 혼난적있음

[익명(223.39)]

경로가 아니라 간선 수

[익명(211.51)]

시간이나 메모리는 상관없을것같은데요

[익명(223.39)]

자세하게 설명해주면 각 상태의 거리값이 (거리)-(더해준 값)*(지나온 간선 수) 가 돼서 안된댔음

[익명(223.39)]

못 알아듣겠으면 국비 등록해라

[익명(223.39)]

예제 가져왓다 1,2,3,4에서 1->4 채단경로 보자: 1->3:1, 3->4:1, 1->4: 0, 1->2: 100, 2->3: -999 이건 아예 안되네 생각해보니까

[익명(211.51)]

경로가 길어질수록 코스트가 늘어나서 안되는구나

[익명(118.34)]

글케 해결될거였으면 벨만포드 알고리즘 안나왔지

[익명(223.39)]

그래도 이런 질문을 생각해봐야 실력이 느는거라고 국비 선생님이 칭찬해줬음