我在一个具有挑战性的问题上卡住了，我在笔记上阅读。
一个无向的、加权的和连通的图G，(没有negative权重并且所有权重都是distinct)，我们知道在这个绘制任何 两个顶点之间的最短路径在最小生成树 (MST) 上。 (对于任何一对顶点和它们之间的任何最短路径，它位于 MST 上)。以下哪项是正确的？
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)
如何验证这些选项？这是一个具有挑战性的问题。
最佳答案
没有。例如:
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 的算法将在第三个顶点之前采用第四个顶点。发生这种情况是因为在处理前两个顶点后第三个顶点更靠近树，但它与起始节点的总距离更大。
关于algorithm - 具体图表和一些关于最短路径的声明？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29537365/