우리는 Dijkstra 's를 사용하여 부 가중치가있는 그래프에서도 최단 경로를 찾을 수 있습니까?

Question

최소 에지 무게가 -100 인 그래프가 있다고 가정 해 보겠습니다. Dijkstra의 알고리즘을 사용하여 모든 가장자리에 100을 오프셋으로 추가 할 수 있습니까?

왜 그런 방법으로 잘못된 해결책을 제공하는지 이해해주십시오.

Answer 1

모든 가장자리 가중치에 100을 추가하면 가장자리가 적은 경로보다 가장자리가 많은 경로에 불이익을주기 때문에 잘못된 솔루션이됩니다.

예를 들어, 그래프가 있고 점 A에서 점 B까지의 최단 경로가 3 개의 모서리와 총 거리 5를 갖고 있다고 가정하십시오. 점 A에서 점 B까지의 다른 경로가 2 개의 모서리를 가지고 있지만 총 거리가 10.

각 에지 가중치에 100을 더하면 첫 번째 경로의 비용은 305이고 두 번째 경로의 비용은 210입니다. 따라서 두 번째 경로는 첫 번째 경로보다 짧아집니다.

따라서 오프셋 및 추가 각 에지 중량 바이어스 반드시 최단 경로를 유지하지 않는다고 결론 내릴 수있다.