Why does Johnson’s algorithm add vertex s to V in its first step? Why not just use any existing vertex in the input graph? Explain, and give an example of a directed graph for which Johnson’s algorithm would not work without adding a vertex s to V in the initial step.

Answer rating: 100% (QA)

Ans Johnsons algorithm is used for finding the shortest paths between all pairs of vertices in a wei... View the full answer