Question: Professor Michener claims that there is no need to create

Professor Michener claims that there is no need to create a new source vertex in line 1 of JOHNSON. He claims that instead we can just use G′ = G and let s be any vertex in V [G]. Give an example of a weighted, directed graph G for which incorporating the professor's idea into JOHNSON causes incorrect answers. Then show that if G is strongly connected (every vertex is reachable from every other vertex), the results returned by JOHNSON with the professor's modification are correct.

$1.99
Sales1
Views641
Comments
  • CreatedJuly 14, 2010
  • Files Included
Post your question
5000