Dijkstra의 알고리즘이 음의 가중치 모서리에서 작동하지 않는 이유는 무엇입니까? 누군가가 단일 소스 최단 경로에 대한 Dijkstra의 알고리즘이 가장자리가 음이 아니어야한다고 가정하는 이유를 말해 줄 수 있습니까? 나는 음의 무게 사이클이 아닌 가장자리 만 이야기하고 있습니다. Dijkstra의 알고리즘에서 일단 정점이 "닫힌"(및 열린 세트에서)으로 표시되면-알고리즘은 최단 경로를 찾았으며이 노드를 다시 개발할 필요가 없습니다. 경로가 가장 짧습니다. 그러나 음수 가중치를 사용하면 사실이 아닐 수 있습니다. 예를 들면 다음과 같습니다. A / \ / \ / \ 5 2 / \ B--(-10)-->C V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)} A의 Dijkst..