我陷入了一个具有挑战性的问题，我在笔记上阅读。
给出了一个无向加权连通图G（不含negative权，所有权都是distinct），我们知道在该图中任意两个顶点之间的最短路径在Minimum Spanning Tree（MST）上。（对于任何一对顶点和它们之间的任何最短路径，它都位于MST上）。以下哪项是True？
1） 图G是一棵树。
2） 每个{u，v}边的权重，至少等于（相同）从u到v的最短路径中的最重边。
3） 任意两个顶点之间的最短路径u，v是唯一的。
4） 假设从顶点
s开始，Prime（用于计算MST）和Dijkstra（用于计算最短路径），处理并添加顶点以相同的顺序排列到它们的树中。（两种算法在处理和添加节点时顺序相同）
如何验证这些选项？这是一个具有挑战性的问题。
-
没有。例如：
V = {1, 2, 3}、E = {(1, 2, 1), (2, 3, 2), (1, 3, 4)}（每条边被编码为元组（一个顶点、另一个顶点和权重））。它不是一棵树，但所有最短路径都在最小生成树上。 -
是的。如果此边的权重小于最短路径中最重边的权重，则此边比最短路径短（因为没有具有负权重的边）。因此，最短的路径不是最短的。这是一个矛盾。
-
否。让我们假设我们有一个图，它有两个顶点
{1, 2}，它们之间有一条边，权重为零。在第一个和第二个顶点（[1, 2], [1, 2, 1, 2], ...）之间有无限多条最短路径*然而，在任何两个顶点之间都有一个唯一的简单最短路径，因为在树中的任何两个节点之间只有一个简单路径，任何不完全位于最小生成树中的路径由于问题陈述而更长，并且在具有不同边权的图中只有一个最小生成树。
-
没有。考虑这个树：
V = {1, 2, 3, 4}，E = {(1, 2, 3), (2, 3, 2), (1, 4, 4)}。假设起始顶点为1。Prim的算法将取第一个顶点，而不是第二个顶点，也不是第三个顶点，然后才取第四个顶点。但是Dijkstra的算法会在第三个顶点之前取第四个顶点。发生这种情况的原因是，在处理前两个顶点后，第三个顶点位于离树更近的位置，但它与起始节点的总距离更大。
我不想给出完整的答案，但以下是如何处理它：
-
你能把边添加到树上，使它不再是一棵树，并且树仍然包含所有最短路径吗？
-
如果有一条边比最重的边短，会发生什么？
-
这是令人困惑的，因为问题说"任何两个顶点之间的最短路径都在MST上"，但没有解决可能存在多个最短路径的事实。所以你可以假设"树上至少有一条最短的路径"。在这种情况下，只需通过MST将两个顶点与一条权重等于成本的边连接起来，就可以得到答案。
-
同样，您应该从如果顶点没有以相同的顺序添加会发生什么开始