2021-09-06

本文主要是介绍2021-09-06，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

这几天复习数据结构，发现在复习Prim算法时，有点迷惑：对于已经松弛好的路径<u,v>，长度为a，是否存在另一个新的顶点（暂时定为x），使得源点u通过连接这个顶点x，再通过x连接v而使得u到v的路径长度缩短到b，即b<a.
这里给出我自己的思考过程，先给出答案：不存在！可利用反证法证明：

假设存在x使得： light(<u,v>)   大于  light(<u,x>)+light(<x,v>)，其中:

	light(<u,v>)=a
	
	light(<u,x>)+light(<x,v>)=b

即(注意图中连线并不代表直接相连，而是代表两点之间的路径) 在这里插入图片描述
a>b,即a>(m+n=b),也就是说m,n一定要小于a才行，可问题是，如果m<a,那么按照prim算法扩展新边时，应该是至少也要选择x并入到V，而不是v并入到V，所以m不可能比a小，假设不成立，证毕。

这篇关于2021-09-06的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程