首页 > 试题广场 >

Michener教授声称,没有必要在JOHNSON算法的第

[问答题]
 Michener教授声称,没有必要在JOHNSON算法的第1行创建一个新的源结点。他主张可以使用G'=G,  并设s为任意结点。请给出一个带权重的有向图例子,使得当将这位教授的想法用到JOHNSON算法中将导致错误的结果。然后,证明:如果图G是强连通的(每个结点都可以从其他每个结点到达),那么使用教授的修改意见后的JOHNSON算法将返回正确结果。

这道题你会答吗?花几分钟告诉大家答案吧!