누군가 단일 소스 최단 경로에 대한 Dijkstra의 알고리즘이 가장자리가 음수가 아니어야한다고 가정하는 이유를 말해 줄 수 있습니까?
나는 음의 가중치주기가 아닌 가장자리에 대해서만 이야기하고 있습니다.
답변
Dijkstra의 알고리즘에서 정점이 “닫힌”(그리고 열린 세트에서 벗어남)으로 표시되면 알고리즘이 최단 경로를 찾았고이 노드를 다시 개발할 필요가 없습니다. 경로가 가장 짧습니다.
그러나 음의 가중치는 사실이 아닐 수 있습니다. 예를 들면 :
A
/ \
/ \
/ \
5 2
/ \
B--(-10)-->C
V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}
A의 Dijkstra는 먼저 C를 개발하고 나중에 찾지 못합니다. A->B->C
좀 더 깊은 설명을 편집 하십시오.
이는 각 완화 단계에서 알고리즘이 “폐쇄 된”노드에 대한 “비용”이 실제로 최소라고 가정하므로 다음에 선택 될 노드도 최소라고 가정하기 때문에 중요합니다.
아이디어는 다음과 같습니다. 비용이 최소화되도록 정점이 열려있는 경우- 임의의 정점에 양수 를 추가하여 최소 성은 절대 변경되지 않습니다.
양수에 대한 제약이 없으면 위의 가정은 사실이 아닙니다.
우리는 “닫힌”각 꼭지점이 최소라는 것을 “알고”있기 때문에-우리는 “뒤를 돌아 보지 않고”이완 단계를 안전하게 수행 할 수 있습니다. “돌아보기”가 필요한 경우 -Bellman-Ford 는 재귀 적 유사 (DP) 솔루션을 제공합니다.
답변
소스가 Vertex A 인 아래 표시된 그래프를 고려하십시오. 먼저 Dijkstra의 알고리즘을 직접 실행 해보십시오.
설명에서 Dijkstra의 알고리즘을 참조 할 때 아래 구현 된 Dijkstra의 알고리즘에 대해 이야기하겠습니다.
따라서 처음에 각 정점에 할당 된 값 ( 소스에서 정점까지의 거리 )은 다음과 같습니다.
먼저 Q = [A, B, C]에서 가장 작은 값, 즉 A를 가진 정점을 추출하고 그 후에 Q = [B, C] . 참고 A에는 B와 C에 대한 방향 에지가 있고 둘 다 Q에 있으므로 두 값을 모두 업데이트합니다.
이제 C를 (2 <5), 이제 Q = [B] 로 추출 합니다. C는 아무것도 연결되어 있지 않으므로 line16루프가 실행되지 않습니다.
마지막으로 B를 추출한 후 
. 참고 B는 C로 향하는 가장자리를 가지고 있지만 C는 Q에 존재하지 않으므로 다시 for 루프를 입력하지 않습니다 line16.
그래서 우리는 거리를
갈 때 A에서 C까지의 최단 거리가 5 + -10 = -5이기 때문에 이것이 어떻게 잘못되었는지 주목하십시오 
.
따라서이 그래프에서 Dijkstra의 알고리즘은 A에서 C까지의 거리를 잘못 계산합니다.
이것은 Dijkstra의 알고리즘이 Q에서 이미 추출 된 정점에 대한 더 짧은 경로를 찾으려고하지 않기 때문에 발생합니다 .
무엇 line16루프가하고있는 것은 정점을 복용이다 U를 하고 말을 우리가 갈 수처럼 “이봐 모습을 V 를 통해 소스에서 U , 더 나은 현재보다 그 (ALT 또는 대체) 거리 [V] DIST 그래서 업데이 트를 할 경우 우리가?있어 dist [v] “
에 있습니다 line16그들은 모두 이웃의 확인 절 (즉, 감독 가장자리에서 존재 U V로 )의 U 있는 Q 여전히 . 에서 line14경우가 Q. 그래서에서 방문 메모를 제거 x는 의 방문 이웃 유 , 경로가 되고 도 고려하지 소스에서 가능한 짧은 방법으로 V .
위의 예에서 C는 방문한 B의 이웃이므로 경로 는 고려되지 않았으며 현재 최단 경로는
변경되지 않았습니다.
이것은 간선 가중치가 모두 양수인 경우 실제로 유용 합니다. 왜냐하면 더 짧을 수없는 경로를 고려하는 데 시간을 낭비하지 않기 때문 입니다.
그래서 나는이 알고리즘을 실행할 때 x 가 y 이전에 Q에서 추출 되면 
더 짧은 경로를 찾을 수 없다고 말합니다 . 예를 들어 설명하겠습니다.
마찬가지로 Y는 단지 추출되었으며 , X는 자체 전에 후 추출했다 DIST [Y]> DIST를 [X] 때문에 다른 예는 이전에 추출 된 것이 X . ( line 13최소 거리 먼저)
그리고 에지 가중치가 양수 라고 이미 가정 했듯이, 즉 length (x, y)> 0 . 따라서 y 를 통한 대체 거리 (alt) 는 항상 더 커야합니다. 즉, dist [y] + length (x, y)> dist [x] . 따라서 y 가 x에 대한 경로로 간주 되더라도 dist [x] 의 값은 업데이트되지 않았을 것입니다 . 따라서 우리 는 여전히 Q 에있는 y의 이웃 만 고려하는 것이 합리적이라는 결론을 내립니다 (의 주석 참고 ).line16
그러나 이것은 양의 가장자리 길이 가정에 달려 있습니다. 만약 length (u, v) <0 이면 그 가장자리가 얼마나 음수인지에 따라에서 비교 후 dist [x]를 대체 할 수 있습니다 line18.
따라서 모든 정점 v 가 제거되기 전에 x 가 제거되면 ( 즉, x 가 음의 가장자리를 연결하는 v 의 이웃 이되도록) dist [x] 계산은 잘못 됩니다.
각 v 정점은 소스에서 x 로의 잠재적 “더 나은”경로에서 두 번째 마지막 정점 이므로 Dijkstra의 알고리즘에 의해 삭제됩니다.
위의 예에서 실수는 B가 제거되기 전에 C가 제거 되었기 때문입니다. 그 C가 B의 이웃 인 반면 음의 가장자리가 있습니다!
명확히하기 위해 B와 C는 A의 이웃입니다. B에는 단일 이웃 C가 있고 C에는 이웃이 없습니다. length (a, b)는 꼭지점 a와 b 사이의 가장자리 길이입니다.
답변
Dijkstra의 알고리즘은 경로가 ‘무거운’경로 만 될 수 있다고 가정하므로 가중치가 3 인 A에서 B 로의 경로와 가중치가 3 인 A에서 C 로의 경로가있는 경우 가장자리를 추가 할 수있는 방법이 없습니다. 3 미만의 가중치로 A에서 B를 통해 C로 이동합니다.
이 가정은 음의 가중치를 고려해야하는 알고리즘보다 알고리즘을 더 빠르게 만듭니다.
답변
Dijkstra 알고리즘의 정확성 :
알고리즘의 모든 단계에서 2 세트의 정점이 있습니다. 세트 A는 최단 경로를 계산 한 정점으로 구성됩니다. 세트 B는 나머지 정점으로 구성됩니다.
귀납적 가설 : 각 단계에서 이전의 모든 반복이 정확하다고 가정합니다.
Inductive Step : 집합 A에 꼭지점 V를 추가하고 거리를 dist [V]로 설정할 때이 거리가 최적임을 증명해야합니다. 이것이 최적이 아닌 경우 길이가 더 짧은 정점 V에 대한 다른 경로가 있어야합니다.
이 다른 경로가 정점 X를 통과한다고 가정합니다.
이제 dist [V] <= dist [X]이므로 그래프에 음의 에지 길이가 없으면 V에 대한 다른 경로는 적어도 dist [V] 길이가됩니다.
따라서 dijkstra의 알고리즘이 작동하려면 간선 가중치가 음수가 아니어야합니다.
답변
다음 그래프에서 Dijkstra의 알고리즘을 A소스 노드 라고 가정 하여 어떤 일이 발생하는지 확인하십시오.
답변
Dijkstra의 알고리즘에서 정점이 “닫힌”(그리고 열린 집합에서 벗어남)으로 표시되면- 그로부터 시작된 모든 노드가 더 먼 거리로 이어질 것이라고 가정 하고 알고리즘이 가장 짧은 경로를 찾았다는 점을 상기하십시오. 이 노드를 다시 개발할 필요는 없지만 음의 가중치의 경우에는 적용되지 않습니다.
답변
지금까지 다른 답변은 Dijkstra의 알고리즘이 경로에서 음의 가중치를 처리 할 수없는 이유를 잘 보여줍니다.
그러나 질문 자체는 경로의 무게에 대한 잘못된 이해에 근거한 것일 수 있습니다. 일반적으로 경로 찾기 알고리즘에서 경로에 대한 음의 가중치가 허용되는 경우 중지되지 않는 영구적 인 루프가 발생합니다.
이걸 고려하세요:
A <- 5 -> B <- (-1) -> C <- 5 -> D
A와 D 사이의 최적 경로는 무엇입니까?
모든 경로 찾기 알고리즘은 B와 C 사이를 지속적으로 반복해야합니다. 그렇게하면 전체 경로의 가중치가 줄어들 기 때문입니다. 따라서 연결에 음의 가중치를 허용하면 각 연결을 한 번만 사용하도록 제한하는 경우를 제외하고는 모든 pathfindig 알고리즘에 문제가 생길 수 있습니다.
