아래 그림에 대한 존슨의 알고리즘을 설명 할 수 있습니까? 알고리즘이 어떻게 작동하는지 혼란 스럽습니다. 나는 이것이 Bellman Ford과 Dijkstra's의 조합이라는 것을 알고 있습니다.존슨의 알고리즘 그래프 설명
그러나 좋은 그래프 설명을 찾을 수 없으므로 단계별로 솔루션을 설명합니다.
다음은 그래프입니다. 
거리에 대한 참고 사항 : f에서 b는 -5 (5가 아님)입니다. g에서 e는 -3 (3이 아님); b부터 d까지는 -5 (5가 아님)
대단히 감사합니다. 먼저 가중치를 변경해야한다는 것을 알고 있지만 가중치를 변경하는 방법은 확실하지 않습니다.
질문 : b에서 c까지 최단 경로를 찾고 싶습니다.
이미 완료 했으므로 다른 노드에 대한 가중치 0 연결로 새 노드를 소개합니다 (z). 우리는 서로 다른 경로로 Z에서 가장 짧은 경로를 해결 얻을 :
h(a) = 0
h(b) = -5
h(c) = 0
h(d) = -10
h(e) = -4
h(f) = 0
h(g) = -1
그런 다음 우리는 가장자리의 가중치 계산 : 짧은 팻 hfrom을 찾을 수
w'(a,d) = w(a,d) + h(a) - h(d) = 11 + 0 - (-10) = 21
w'(b,a) = w(b,a) + h(b) - h(a) = 7 + (-5) - 0 = 2
w'(b,d) = w(b,d) + h(b) - h(d) = -5 + (-5) - (-10) = 0
w'(c,a) = w(c,a) + h(c) - h(a) = 17 + 0 - 0 = 17
w'(c,b) = w(c,b) + h(a) - h(b) = 3 + 0 - (-5) = 8
w'(d,f) = w(d,f) + h(d) - h(f) = 12 + (-10) - 0 = 2
...
어떻게 h (a)를 h (g)로 하였습니까? – JavaLeave
@KellyAnn : 그 부분이 있다고 생각했습니다. 텍스트는 [Bellman-Ford 알고리즘] (http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm#Algorithm)을 사용한다고 말하면서 (실제로 모르겠습니다). 필자는 연필과 종이로 그랬지만 필자는 그것을 모른 채 Bellman-Ford 알고리즘을 사용했을 수도 있다고 생각한다. 모든 0으로 시작한 다음 개선 할 수있는 부분을 찾았습니다. – Beta
고마워요! 나는 혼란스러워하는 것이 Bellman-ford에 관한 것이라고 생각한다. 나는 위키 페이지를 살펴볼 것이다. 존슨에 대한 모든 설명을 해주셔서 감사합니다. 정말 고마워요 :) – JavaLeave
존슨은 다음과 같은 3 단계를 수행합니다. 1) 새 노드를 도입하고 새 노드에서 모든 이전 노드로가는 최단 경로를 계산합니다. 2) 가중치를 변경합니다. 3) b에서 c로 최단 경로를 찾습니다. 2 단계는 문제가있는 것입니까? – Beta
@ 베타 예. 나는 무게를 바꾸는 데 문제가있다. 나는 공식이 w '(u, v) = w (u, v) + h (u) -h (v)라는 것을 알고 있긴하지만 그것을 어떻게 바꾸는 지에 대해 정말로 혼란 스럽다. 그러나 존슨의 알고리즘 예제에 대한 Cormen의 Intro to Algorithm 장을 읽었을 때 실제로 혼자 힘으로 파악할 수 없었습니다. 누군가가 나를 도울 수 있기를 바랍니다. – JavaLeave