给出了一个无向、加权、连通图G（无负权且所有权是不同的），图上任意两点之间的最短路径在最小生成树上。
然后：
图g是一棵树。
II）每个{u，v}边的重量至少等于
从U到V的最短路径。
iii）任何两个顶点之间的最短路径u，v是唯一的。
iv）假设从顶点s开始，prime（用于计算mst）和dijkstra（用于计算最短路径），处理并添加
顶点成树，顺序相同。（两个算法处理和添加节点的顺序相同）
请解释一下，为什么只有两个说法是真的？我对助教提出的定义感到困惑。
最佳答案
设G=(V,E,w)为具有以下性质的加权图。
w(e)>=0代表每个e in E和w(e1) != w(e2)代表每个e1,e2 in E和e1 != e2。
对于每个a,b in V，对于每个最短路径p从a到b在G中存在一个最小生成树T > cc>使得G包含在p中。
请注意，属性2在需求中没有完全清楚地说明，但据我所知，这就是op的含义，因为其他解释实际上没有意义：如果对于任何一对顶点T和a，它们之间有两条最短路径b和p1，它们就不能包含在同一个最小生成树中，因为它们会形成一个循环。同样，在p2和p之间给出最短路径a，不一定存在包含b的最小生成树。
那么，陈述一）和四）不一定是真的，但陈述二）和三）是真的。
对于语句I），考虑下面的反例让p与G:=(V,E,w)，V:={1,2,3}和
w({1,2}):=1,
w({1,3}):=2,
w({2,3}):=4.
请注意，所有边权重都是正的且不同，因此满足上面的属性1此外，边E:={{1,2},{1,3},{2,3}}和{1,2}构成{1,3}的唯一最小生成树。最后，从T到G的唯一最短路径是1，从2到{1,2}的唯一最短路径是1，从3到{1,3}的唯一最短路径是2。所有这些路径都包含在3中。但是，{2,1}{1,3}包含循环，因此它不是树。
对于语句ii），让T。让G成为{1,2},{2,3},{3,1}中从u,v in V到p的最短路径假设u小于中最大权重的边。然后v是从G到w({u,v})的路径，其权重小于p的总权重，这必须大于{u,v}，因为所有边权重都是正的这意味着u不是v中从G到p的最短路径，这是一个矛盾。
对于语句iii），请注意，最小生成树是唯一确定的；这与prim算法的工作原理一致，因为上面属性1的不同边权重使最轻边的选择具有确定性。或者，这可以通过论证每个生成树必须包含最小权重w({u,v})的边来归纳地看到。总之，由于最小生成树p是唯一确定的，因此每个u只能有一条从v到G的最短路径，因为每个最短路径必须包含在G中如果存在两条这样的路径，则T有一个循环，情况并非如此。
对于语句iv），请考虑以下反例。设u其中v，G和
w({1,2}):=01,
w({1,3}):=04,
w({2,3}):=10,
w({2,4}):=03,
w({3,4}):=09.
假设Prim和Dijkstra从节点u,v in V开始。然后，边构成Prim在序列中生成的唯一确定的最小生成树。
路径T是从T到G:=(V,E,w)的唯一最短路径，V:={1,2,3,4}是从E:={{1,2},{1,3},{2,3},{2,4},{3,4}}到1的唯一最短路径；{1,2},{2,3},{3,4}是从T到1,2,4,3的唯一最短路径，{1,2}是从1到2的唯一最短路径。此外，{1,3}是从1到3的唯一最短路径，{1,2}{2,4}是从1到4的唯一最短路径。总共，{4,2}{2,1}{1,3}具有上面的属性1和2。
Dijkstra的选择如下，其中4表示无穷大。
Node 1 2 3 4 tentative distance 00 01 04 ++ discovered y n n n => select node 2 Node 1 2 3 4 tentative distance 00 01 04 04 discovered y y n n => select node 3 (could also select 4, as Prim, but selects 3) Node 1 2 3 4 tentative distance 00 01 04 04 discovered y y y n => select node 4
总的来说，所选节点的序列是3，这与prim生成的序列不同。