Johnson Algoritması grafiği açıklaması

Question

Aşağıdaki grafik için Johnson algoritmasını açıklayabilir mi? Algoritmanın nasıl çalıştığı konusunda gerçekten kafam karıştı. Bunun Bellman Ford ve Dijkstra's'un bir kombinasyonu olduğunu biliyorum.

Ancak, iyi bir grafik açıklaması bulamıyorum, bu çözüm adım adım açıklıyor.

İşte grafik.

Mesafelerle ilgili not: f'den b'ye -5 (değil 5); e'ye e3 (3 değil); d, -5 (değil 5)

Çok teşekkür ederim. İlk önce ağırlıkları değiştirmem gerektiğini biliyorum, ancak ağırlıkların nasıl değiştirileceğine gerçekten emin değilim.

Soru: b - c arasındaki en kısa yolu bulmak istiyorum.

Answer 1

Zaten yaptığınız gibi, yeni bir düğüm tanıtıyoruz, diğer tüm düğümlere ağırlık-0 bağlantıları ile z olarak adlandırıyoruz. Her diğer yolu z en kısa yollar üzerinden çalışır ve elde:

h(a) = 0 
h(b) = -5 
h(c) = 0 
h(d) = -10 
h(e) = -4 
h(f) = 0 
h(g) = -1 

Sonra kenarlarının ağırlıkları yeniden hesapla: kısa pat hfrom bulmak için

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 
... 

sonra Dijkstra kullanımı ila b. Bu örtüyor mu?