Spiegazione del grafico dell'algoritmo di Johnson

Question

Qualcuno può spiegare l'algoritmo di Johnson per il grafico sottostante? Sono davvero confuso su come funziona l'algoritmo. So che è una combinazione di Bellman Ford e Dijkstra's.

Ma non riesco a trovare una buona spiegazione grafica, che spieghi la soluzione passo dopo passo.

Questo è il grafico.

Nota relativa alle distanze: da f a b è -5 (non 5); g a e è -3 (non 3); da b a d è -5 (non 5)

Grazie mille. So che prima devo cambiare i pesi, ma non sono sicuro di come cambiare i pesi.

Domanda: Voglio trovare il percorso più breve da b a c.

Answer 1

Come abbiamo già fatto, introduciamo un nuovo nodo, lo chiamiamo z, con connessioni peso-0 per tutti gli altri nodi. Lavoriamo i percorsi più brevi da z l'un l'altro percorso e otteniamo:

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

Poi abbiamo ricalcolare i pesi dei bordi:

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

quindi utilizzare Dijkstra per trovare il più breve hdalle pat a a b. Questo lo copre?