원본 (S)을 남기는 가장자리를 제외한 모든 음이 아닌 가장자리를 가진 방향 그래프가 있습니다. 다른 정점에서 소스까지의 모서리가 없습니다. 그래프에서 소스 (S)에서 정점 (T)까지의 최단 거리를 찾으려면 원본을 떠나는 가장자리가 음수 임에도 불구하고 Dijkstra의 최단 경로 알고리즘을 사용할 수 있습니까?그래프에 Dijkstra의 최단 경로 알고리즘을 사용할 수 있습니까?
소스 인접 에지에만 음의 가중치가있을 수 있으며 원본 인접 노드에서 소스로 돌아가는 경로가 없다고 가정하면 (주석에 언급 된 바와 같이) 모든 상수에 상수 C를 추가 할 수 있습니다. 그것들을 모두 부정적으로 만들 수있는 출처. 그런 다음 최종 결과에서 C을 뺍니다.
더 일반적으로 Dijkstra는 Johnson's reweighting algorithm (본질적으로 Bellman-Ford이지만 한 번만 수행해야 함)을 적용한 후 음의 에지 가중치 (음수 사이클 없음)가있는 그래프에서 최단 경로를 푸는 데 사용할 수 있습니다).
일반적으로 음수 링크가있는 (지시 된) 그래프에 Dijkstra의 알고리즘을 사용할 수없는 이유는 Dijkstra의 알고리즘이 욕심이 많기 때문입니다. 최소 거리의 버텍스를 선택하면 나중에에 도달 할 수있는 방법이 없다고 가정합니다.
첫 번째 단계가 끝난 후 특정 그래프에서 가능한 모든 음의 모서리를 가로 지르고 Dijkstra의 가정은 실제로 지금부터 유지됩니다. 시작점에 직접 연결된 꼭지점이 음수 값을 가지고 있다는 사실에 관계없이 어느 것이 최소 거리인지 식별하면 더 적은 거리로 다시 도달 할 수 없습니다 (이 지점에서 가로 지르는 모든 가장자리는 양수 값을 가지므로 거리).
예, 해당 유형의 유향 그래프에서 Dijkstra를 사용할 수 있습니다.
Dijsktra에 대해 이미 완료된 alghoritm을 사용하고 음수 값을 사용할 수없는 경우 가장 낮은 음의 끝을 찾아 모든 시작 가장자리에 추가하는 것이 좋습니다. 따라서 음수가 전혀 없습니다. 끝내면 그 수를 빼냅니다.
코드를 직접 작성하면 (코드는 매우 간단하고 권장합니다.) 거의 아무것도 변경하지 않고, 가장 낮은 값으로 시작하여 (Dijkstra의 경우처럼) 허용합니다. 가장 낮은 값은 부정. 그것은 당신의 경우에 작동합니다.
@ NiklasB. - 부정적인 사이클이 없다, 질문의 코멘트를 보라. – libik
나는 그것을 지금 본다, thanks –
dijkstra의 알고리즘이 알고리즘의 가장자리에 적용되는 조건을 생각하면 초기화 후 절대 감소하지 않는 것입니다.
따라서 첫 번째 단계가 음수 일 경우 실제로는 문제가되지 않습니다. 그 이유는 함수가 계속 증가하여 올바른 출력을 찾을 수 있기 때문입니다 (시작 사각형으로 돌아갈 방법이없는 경우).).
좋은 점, 나는 실제로 그것을 생각하지 않고 있었다. 그러나 내가 생각하는 "올바른 산출물이 발견 될 것"이라고 생각한다. (최단 경로가없는 것처럼, 올바른 출력이어야 함). 나는 그것에 대해 정확하게 생각하고 있는가? –
OP는 인접 노드 중 하나에서 소스로 되돌아가는 경로가있을 가능성을 명시 적으로 제외 시켰으므로 소스와 관련된 사이클이 없을 수 있습니다. 나는 지금 그것을 깨달았다. –
노드 S1에서 네거티브 에지를 통해 노드 S2로 이동 한 다음 다른 네거티브 에지를 통해 S1로 돌아갈 수 있습니까? 또는 시작하면 시작 노드 S1로 다시 돌아갈 수 없습니까? – libik
다른 꼭지점에서 가장자리까지 가장자리가 없으므로 그래프의 다른 노드에서 소스로 돌아갈 수 없습니다. – Neel
즉, 시작 노드에서 다른 노드까지의 에지는 항상 방향을 가지고 있다는 것을 의미합니까? – libik