Dijkstra의 알고리즘에서 추출 된 거리 값이 감소하지 않는다는 것을 증명합니까?

Question

이전 알고리즘 노트를 검토 중이며이 증거를 발견했습니다. 내가 가진 임무에서 나온 것이고 정확하다고 생각되지만, 그 증명이 확실하게 결여되어 있다고 느낍니다.

증명 모순 :

문제는 다음과 같이 내 증거가 간다

prove that the distance values taken from the priority queue in Dijkstra's algorithm is a non-decreasing sequence.이다. 주먹, 우리가 d 값 'i'와 Q에서 정점을 당기는 가정하십시오. 다음에 우리는 정점을 d 값 'j'로 당깁니다. 우리가 을 가져 왔을 때 우리는 d- 값을 확정하고 시작점 s에서 i까지의 최단 경로 을 계산했습니다. 이후 우리는 양의 가장자리 가중치를 가지고 있으므로 우리의 경로에 정점을 추가 할 때 우리의 d 값을 줄이는 것은 불가능합니다. 을 Q에서 가져온 후 으로 j를 끌어 당기면 이 i부터 j까지 도달 할 수 있으므로은 i에 대한 최단 경로가 이되지 않을 수 있습니다. 그러나 우리는 이미 i에 대한 가장 짧은 경로 인 을 계산했습니다. 가능한 경로를 확인하지 않았습니다. 더 이상 경로가 보장되지 않습니다. 모순.

이 증명을 어떻게 개선 할 수 있습니까? 아니면 더 나은 방법이 있습니까? 그것은 단지 매우 약한 :) 보인다

편집 : 죄송합니다,이 경우 내 우선 순위 큐는

Answer 1

이의이 (이러한 설정하자 최소 힙 구현이 그들이 있기 때문에, 기본적으로, 모두 해당 알고리즘의 정의) :

1. 다 익스트라의 알고리즘에 우선 순위 큐는 당신에게 알고리즘의 각 반복에서 가장 낮은 D-값을 가진 노드를 제공 할 것입니다.
2. 음수 에지 가중치가 없습니다.
3. 일단 노드가 대기열에서 제거되면 대기열로 되돌아 가지 않습니다.
4. 대기열에서 제외 된 노드의 d 값은 최종 값이며 그 시점부터 변경되지 않습니다.

계속하기 (1), 그 대기열에서 노드 D 값, 가정 (2) 적용 추출 이전 D 값에 적어도 동일있을 것 각 노드의 D 값은 의존하기 때문에 이전에 대기열에서 제외 된 노드의 d 값에 대해 재귀 적으로 정의됩니다. (3)과 (4)가 맞으므로이 재귀 적 정의는 0의 d 값을 갖는 시작 노드에서 끝납니다.
따라서 각 노드의 d 값이 적어도 그 전에있는 d 값과 같으면 , (1)이 여전히 적용되면 우선 순위 큐에서 추출 된 d- 값 집합은 비 감소입니다.

(이 통해 읽기, 당신이 쓴 후에는 기본적으로 동일하지만 내 생각은 조금 더 나은 발표) 우선 순위 큐 구현이 정의되지 않은 다 익스트라의 알고리즘의 고전 의사 구현에서는