具体图表和一些关于最短路径的声明？
Specific Graph and some claims on shortest path?
我在一个具有挑战性的问题上卡住了，我在笔记上看了。
给出一个无向加权连通图G，（没有negative权重，所有权重都是distinct），我们知道在这个图中[=之间的最短路径24=]any 两个顶点在 Minimum Spanning Tree (MST) 上。 （对于任何一对顶点和它们之间的任何最短路径，它位于 MST 上）。以下哪个是 True?
1) Graph G is a Tree.
2) weight of each {u,v} edge, at least is equal (same) to heaviest edge in shortest path from u to v.
3) shortest path between any two vertex u, v is unique.
4) suppose start from vertex s, Prime (for calculating MST) and Dijkstra (for calculating shortest path), process and add the
vertexes into their Trees, with the same order. (two algorithm works with same order in processing and adding node)
如何验证这些选项？这是一个具有挑战性的问题。
我不想给出完整的答案，但这是您的处理方式：
你能否将边[s]添加到树中，使其不再是树，并且树仍然包含所有最短路径？
如果有一条边比最重的边短会怎样？
令人困惑，因为问题是 "the shortest path between any two vertexes is on MST"，但没有解决可能存在多个最短路径的事实。所以你可以假设 "at least one shortest path lies on the tree"。在这种情况下，只需通过 MST 将两个顶点与一条权重等于成本的边连接起来，就可以得到答案。
同样，您应该从如果顶点未按相同顺序添加会发生什么开始
没有。例如：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 的算法将在第三个顶点之前采用第四个顶点。发生这种情况是因为在处理前两个顶点后第三个顶点更靠近树，但它与起始节点的总距离更大。
我在一个具有挑战性的问题上卡住了，我在笔记上看了。
给出一个无向加权连通图G，（没有negative权重，所有权重都是distinct），我们知道在这个图中[=之间的最短路径24=]any 两个顶点在 Minimum Spanning Tree (MST) 上。 （对于任何一对顶点和它们之间的任何最短路径，它位于 MST 上）。以下哪个是 True?
1) Graph G is a Tree.
2) weight of each {u,v} edge, at least is equal (same) to heaviest edge in shortest path from u to v.
3) shortest path between any two vertex u, v is unique.
4) suppose start from vertex
s, Prime (for calculating MST) and Dijkstra (for calculating shortest path), process and add the vertexes into their Trees, with the same order. (two algorithm works with same order in processing and adding node)
如何验证这些选项？这是一个具有挑战性的问题。
我不想给出完整的答案，但这是您的处理方式：
你能否将边[s]添加到树中，使其不再是树，并且树仍然包含所有最短路径？
如果有一条边比最重的边短会怎样？
令人困惑，因为问题是 "the shortest path between any two vertexes is on MST"，但没有解决可能存在多个最短路径的事实。所以你可以假设 "at least one shortest path lies on the tree"。在这种情况下，只需通过 MST 将两个顶点与一条权重等于成本的边连接起来，就可以得到答案。
同样，您应该从如果顶点未按相同顺序添加会发生什么开始
没有。例如：
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 的算法将在第三个顶点之前采用第四个顶点。发生这种情况是因为在处理前两个顶点后第三个顶点更靠近树，但它与起始节点的总距离更大。