Johnson's Algorithm graph explanation

Question

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

But I am unable to find a good graph explanation, that explains the solution step by step.

Here is the graph.

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

Thank you very much. I know that I have to change the weights first, but I am not really sure as to how to change the weights.

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

Answer 1

As you've already done, we introduce a new node, call it z, with weight-0 connections to all other nodes. We work out 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 edges:

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 that cover it?