Proof 对于顶点 s 及其最短路径树 T s，MST T 中的楔形是w（ s ， v ），并假设它在 T 中不存在 . 然后必须有一条从 v 到 s 的较短路径，并且路径中有一个顶点（因为w（ s ， v ）不是最短路径），假设为 p ，并使 s - > p - > v ，w（ s ， v ）> =路径（ s - > p - > v ） . 删除w（ s ， v ）并在 T 中添加w（ s ， p ），当所有边缘均为正且不同时，w（ s ， p ）<w（ s ， v ） . 我们得到一个较小的最小生成树 T ' .
但 T 是一个MST . 这是矛盾 . 假设不成立，这证明 T 和 T 必须共享至少一个边，并且它在MST T 中是w（ s ， v ） .
当一些权重为负且w（ s ， p ）> w（ s ， v ）时，即w（ p ， v ）<0，w（ s ， v ）> =路径（ s - > p - > v ）不能使w（ s ， p ）<w（ s ， v ） . 但是在MST T 中，w（ s ， v ）也应该不存在，因为路径（ s - > p - > v ）使 s 变为 v 更低的成本，用W（ s ， p ）和w（ p ， v ）替换W中的w（ s ， v ），如果需要，可以减少最小生成树 T ' . 仍然矛盾 .
2 回答
我认为这句话实际上是正确的，所以我怀疑你能找到一个反例 .
这是一个提示 - 获取图中的任何节点并找到该节点的最短路径树 . 现在考虑如果你从那个节点开始运行Prim's algorithm会发生什么 - 你能保证MST中至少有一个边缘会进入最短路径树吗？
希望这可以帮助！
Proof 对于顶点 s 及其最短路径树 T s，MST T 中的楔形是w（ s ， v ），并假设它在 T 中不存在 . 然后必须有一条从 v 到 s 的较短路径，并且路径中有一个顶点（因为w（ s ， v ）不是最短路径），假设为 p ，并使 s - > p - > v ，w（ s ， v ）> =路径（ s - > p - > v ） . 删除w（ s ， v ）并在 T 中添加w（ s ， p ），当所有边缘均为正且不同时，w（ s ， p ）<w（ s ， v ） . 我们得到一个较小的最小生成树 T ' .
但 T 是一个MST . 这是矛盾 . 假设不成立，这证明 T 和 T 必须共享至少一个边，并且它在MST T 中是w（ s ， v ） .
如果有一个0成本的重量，情况是相似的 . 您可以假设w（a，b）= 0的两个顶点是相同的顶点，并删除其中一个顶点 . 当权重为非负时，证明有效 .
当一些权重为负且w（ s ， p ）> w（ s ， v ）时，即w（ p ， v ）<0，w（ s ， v ）> =路径（ s - > p - > v ）不能使w（ s ， p ）<w（ s ， v ） . 但是在MST T 中，w（ s ， v ）也应该不存在，因为路径（ s - > p - > v ）使 s 变为 v 更低的成本，用W（ s ， p ）和w（ p ， v ）替换W中的w（ s ， v ），如果需要，可以减少最小生成树 T ' . 仍然矛盾 .