다익스트라 알고리즘에서 "지금까지 탐색하지 않은 정점 중 거리 값이 가장 낮은 정점"을 뽑는 이유는 더 이상 그 정점의 거리 값을 더 낮은 값으로 갱신할 일이 없기 때문입니다. 현재 보고 있는 정점이 v이고, v를 탐색했을 때 이미 탐색했던 정점 u의 거리 값을 갱신하려면 v의 거리 값이 u보다 낮아야 되는데 (모든 간선의 가중치가 0 이상이므로...), 그러면 v가 u보다 먼저 탐색되었을 것이므로 모순입니다.

음수 가중치가 있으면 이 특징이 깨져서 다익스트라 알고리즘이 통하지 않습니다.

그럼 "지금까지 탐색하지 않은 정점 중 거리 값이 가장 낮은 정점" 이 아니라 "정점 중 거리 값이 가장 낮은 정점"을 뽑는다면, 음수 가중치 그래프에서 최단 경로를 구하는 것이 가능한가요? 

그러면 같은 정점만 반복해서 뽑고 무한루프를 탈 것 같습니다.

일단 음수 사이클은 없다고 가정해보면

"정점 중 거리 값이 가장 낮은 정점"을 뽑을 때, "지난번에 뽑혔을 때와 거리 값이 동일한 정점은 제외" 하면 불가능 하진 않습니다.

예를 들어 두 번째 정점을 거리 값이 3일 때 뽑아서 처리 했다면, 이 거리 값이 갱신되기 전까진 (3보다 작아지기 전까지) 기존과 같이 뽑기에서 제외하다가,

3보다 작아지면 그때부터 다시 뽑기 후보군에 포함시켜야 합니다.

(만일 갱신되기 전에도 뽑기 후보군에 포함시키면 윗 분의 댓글처럼 무한루프를 돌겠죠.)

음수 사이클이 없다면 이 '갱신' 의 횟수가 유한하기 때문에, 불가능하진 않습니다.

하지만 음수 가중치일때 사용하는 벨만 포드 알고리즘에 비해 논리적으로 복잡하면서 동시에 시간 복잡도도 더 높기 때문에

잘 사용하지 않는 방법입니다.

위에 음수를 가지는 가중치 자체가 실세계에서 얼마나 말이 안되는지는 잘 설명을 해주신거 같구요.. 정답은 될 수 없습니다만, 조금 회피하는 방법을 설명드리면, 심플한 방법도 있죠.. 가장 낮은 음수를 가지는 엣지의 음값 만큼, 모든 엣지에 수를 더한 후 구하면 됩니다.

물론 위의 방법 또한 가중치가 음수라는 것만큼 말이 안되는 방법이긴 합니다.

가장 낮은 음수를 가지는 엣지의 음값만큼 모든 엣지에 더해주면 더 많은 엣지를 거치는 더 짧은 경로가 탐색이 되지 않을 것 같습니다. 더 긴 경로일수록 더해준 값이 누적되어 가중치가 크게 늘어나기 때문이죠. 원하는 답과 전혀 다른 답을 구하게 될 것 같습니다.

참고로 업데이트될 때마다 priority queue에 넣게 하면, 음수 사이클이 없으면서 음수 가중치가 있는 그래프에서 최악의 경우 지수 시간이 걸립니다. 이를 증명하는 그래프를 만드는 문제가 대회에 출제된 적이 있습니다.

https://ipsc.ksp.sk/2015/real/...

바로 윗분이 말씀하신 문제가 백준에도 있네요. 27676번(https://www.acmicpc.net/proble...), 27675번(https://www.acmicpc.net/proble...). 여기(https://kangworld.tistory.com/...)랑 영문 위키피디아도 좋은 내용이 있고요.

구글에 다익스트라 음수 쳤더니 여기가 나와서 오래 됐지만 댓글 남깁니다. 제 생각을 써보자면

1. 음수 사이클이 없고 음수 간선이 있는 상황에서, 다익스트라 (특정) 구현은 복잡하지 않습니다. 아마 99% 사람은 이미 이렇게 구현하고 있을걸요.

2. 시간 복잡도가 대략 O(2^V)입니다.

3. 최단 경로를 올바르게 찾을 수 있습니다.

종합하자면 탈출 조건을 충분히 큰 값(2^V)으로 설정하고 음수 사이클이 없다면, 음수 간선에 대응 가능한 다익스트라를 쉬운 구현으로 매우 느리게 쓸 수 있는 것 같습니다.