주어진 꼭지점에 대한 모든 최단 경로

Question

방향성 그래프 G = (V, E)와 가중치 함수 w : E -> R + (그래프의 가장자리에 대한 양수 하중 만)가 ​​주어지면 모든 최단 경로 V 내의 모든 정점 v로부터 주어진 정점 k까지.

그래프의 가장자리를 뒤집은 다음 버텍스 k에서 Dijkstra's algorithm을 실행하는 방법을 생각해 보았습니다. 나는 k에서 v1까지의 최단 경로 p가 실제로 v1에서 k 로의 가장 짧은 경로인지 (원래의 그래프를 뒤집기 전에) 궁금하다.

누군가가 왜 그런지, 왜 그런지 설명 할 수 있다면 고맙겠습니다.

미리 감사드립니다.

Answer 1

(이것은 세계에서 가장 공식적인 증거는 아니지만 자신을 설득하기에 충분할 것으로 기대됩니다.)

길이 m이며, 그래프 G에서 정점 V 말할 K-V에서 최단 경로를하자. 당신이 알고 싶은 두 가지 사항
반전 된 그래프에서 1. G *가, V-K에서 길이 m의 경로가있다. 반전 그래프
2. G * 미만 m있다 V-K로부터 경로가 없다. 당신이w 을 정점 정점 V에서 직접 경로가있는 경우, 당신은 다음 경로에있는 모든 가장자리 역 :
보조 정리 1 :

나는 시작하기 전에, 우리는 믿음에 한 가지를 취할 수 있습니다 정점 w부터 정점 까지의 경로가 있습니다.입니다. 이것은 증명할 수 있지만, 나는 그것이 상당히 상식이라고 생각합니다. 네가 나를 원한다면 나는 그것을 증명할 것이다. 포인트 1 용

: m 가장자리 이루어진 K-V에서 G의 경로를 고려한다. 이러한 에지들 각각을 반전하는 경우 (보조 정리 1에 의해) 길이 미터의 V에 K로부터 경로를 가질 것이다. 시점 2의

: K에서 길이N < 미터의 V로 반전 된 그래프 G *에서의 경로가 존재한다고 가정. 이 경로를 반대로하면, K-V에서 길이N의 경로 (보조 정리 1)가있다.이 길이의 경로 미터 최단라는 문장을 모순 미만 m 원문 그래프 K-V에서 경로가 있음을 의미한다.