Johnson's graph explanation

Question

Can anyone explain the Johnson algorithm for the graph below? I am really confused about how the algorithm works. I know this is a combination of Bellman Ford and Dijkstra's .

But I cannot find a good explanation of the graph that explains the solution step by step.

Here is the schedule.

Note on distances: from f to b - -5 (not 5); g to e is -3 (not 3); b - d - -5 (not 5)

Thank you very much. I know that I need to change weight first, but I'm not sure how to change weight.

Question: I want to find the shortest path from b to c.

Answer 1

As you have already done this, we introduce a new node, call it z , with connections weighing 0 with all other nodes. We develop the shortest paths from z to each other path and get:

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

Then we recalculate the weights of the ribs:

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

Then use Dijkstra to find the shortest pat hfrom a to b . Does it cover him?