수정 된 그래프에서 Dijkstra의 알고리즘을 실행하고 원래의 거리를 얻기 위해 추가 된 가중치를 뺄 수 있습니까?

Question

음수 에지 가중치를 갖는 그래프를 음수 가중치를 갖지 않는 그래프로 변환하려면 다음 전략을 고려하십시오. 그래프에서 음의 최대 가중치를 -k로합시다. 그런 다음, 가중치가 w 인 그래프의 각 에지에 대해 가중치를 w + k + 1로 업데이트하십시오. 다음과 같은 주장을 고려 :

는 원래의 그래프에서 최단 경로 문제를 해결하기를, 우리가 수정 된 그래프 다 익스트라의 알고리즘을 실행하고 원래

에게 주장을 얻을 수있는 추가 무게를 뺄 수는

일반적으로 사실이 아니다

주장은 모든 그래프

주장 연결된 비순환 그래프

주장 마찬가지이다 사이클 연결된 그래프의 일반적으로 그렇지 않다 마찬가지이다.

Answer 1

일반적으로 사실이 아닙니다 : 노드 A, B, C 및 호 A -> B, A -> C, B -> C의 그래프를 가중치 1,1, -1의 순서로 고려하십시오. A에서 C까지의 최단 경로는 A -> B -> C이고 가중치는 0입니다.이 전략은 모든 가중치에 2를 더하여 A -> C를 더 짧게 만듭니다 (가중치 3).