大门|大门-CS-2016（第1组）|问题24

设G是一个带不同正边权的加权连通无向图。如果每个边权重都增加了相同的值，那么以下哪项陈述是正确的？

P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does not change

（A） 仅P

（B） 仅Q （C） P和Q都不是 （D） P和Q 答复: （A） 说明： 最短的路径可能会改变。原因是，从s到t的不同路径中可能有不同数量的边。例如，最短路径的权重为15，有5条边。假设有另一条路径有两条边，总重量为25。最短路径的权重增加5*10，变成15+50。另一条路径的权重增加2*10，变成25+20。因此，最短路径变为另一条路径，权重为45。

最小生成树不变。还记得Kruskal算法吗？我们先对边进行排序。如果我们增加所有权重，那么边的顺序就不会改变。 这个问题的小测验 如果你在上面的帖子中发现任何错误，请在下面发表评论