For the Johnson’s Algorithm pseudocode provided, prove that the running time is
ID: 3902276 • Letter: F
Question
For the Johnson’s Algorithm pseudocode provided, prove that the running time is O(VE lg V). Considering Bellman-Ford algorithm runs in time O(VE) and the Dijkstra/LCFS algorithm runs in time O(E lg V).
______ Compute G’ as V[G’] = V[G] ? {s} and E[G’] = E[G} ? {s,v}, ?v?V[G]
______ If (Bellman-Ford( G’, w, s ) == false // cycle
______ Report negative-weight cycle and exit
______ Else
______ For each vertex v?V[G’
______ h(v) = ?(s,v) as computed by Bellman-Ford
______ For each edge (u,v) ?E[G’]
______ ?(u,v) = w(u,v) + h(u) – h(v)
______ For each vertex u?V[G]
______ Run Dijkstra(G, ?, u) to get ?(u,v) ?v?V[G] // wt under ?
______ For each vertex v?V[G]
______ ?(u,v) = ?(u,v) + h(v) – h(u)
Explanation / Answer
Here the Johnson’s Algorithm calls Bellman-Ford algorithm once with O(VE) time complexity,
Then in 10th step it calls Dijkstra's algorithm with time complexity O(E lg V) for V times.
So the overall time complexity will be O(VE)+ O(V(E lg V))
= O(VE)+ O(VE lg V)
= O(VE lg V), because O(VE) < O(VE lg V)