图表和PRIM和DIJKSTRA问题？
我们给出一个无向，加权和连通图G（没有负权重和所有权重是不同的），图中任意两个顶点之间的最短路径在最小生成树上。 然后：
I）图G是一棵树。
II）每个{u，v}边的权重至少等于从u到v的最短路径中最重的边。
III）任何两个顶点之间的最短路径u，v是唯一的。
IV）假设从顶点s ，Prime（用于计算MST）和Dijkstra（用于计算最短路径）开始，以相同的顺序处理和添加顶点到树中。 （两个算法在处理和添加节点时以相同的顺序工作）
请解释一下，为什么只有两个这样的声明是真的？ 我很困惑这个定义，由我们的TA提出。
令G=(V,E,w)为具有以下属性的加权图。
对于e in E每个e in E 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的G使得p包含在T 。
请注意，属性2在要求中没有完全清楚地陈述，但就我的理解而言，这是OP的意思，因为其他解释实际上并不合理：如果对于任何一对顶点a和b ，有两个它们之间的最短路径p1和p2不能包含在同一个最小生成树中，因为它们会形成一个循环。 类似地，在最短路径p之间的a和b ，也并不一定存在一个最小生成树包含p 。
那么，陈述I）和IV）不一定是正确的，但陈述II）和III）是正确的。
对于陈述I），请考虑以下反例。 让V:={1,2,3} ， E:={{1,2},{1,3},{2,3}}和G:=(V,E,w)
w({1,2}):=1,
w({1,3}):=2,
w({2,3}):=4.
请注意，所有的边权重是正的和不同的，因此上面的属性1是满足的。 此外，边{1,2}和{1,3}构成G的唯一最小生成树T 最后，从1到2的唯一最短路径是{1,2} ，从1到3的唯一最短路径是{1,3} ，从2到3的唯一最短路径是{2,1}{1,3} 。 所有这些路径都包含在T 。 然而， G包含循环{1,2},{2,3},{3,1} ，因此它不是一棵树。
对于陈述二），让u,v in V 。 设p是G从u到v的最短路径。 假设w({u,v})小于p中最大权重的边。 那么{u,v}是G从u到v的路径，其权重小于p的总权重，因为所有边权重都是正的，所以它必须大于w({u,v}) 。 这意味着在G ， p不是从u到v的最短路径，这是一个矛盾。
对于声明III），注意最小生成树是唯一确定的; 这从Prim算法的工作得出，因为来自上面的属性1的不同边缘权重使得最轻边缘的选择是确定性的。 或者，可以通过论证每个生成树必须包含G的最小权重的边来归纳地看出这一点。 总而言之，由于最小生成树T是唯一确定的，因此对于每个u,v in V v在G只能有一条从u到v最短路径，因为每条最短路径必须包含在T 。 如果存在两条这样的路径，则T有一个循环，事实并非如此。
对于声明四），请考虑以下反例。 令G:=(V,E,w)其中V:={1,2,3,4} ， E:={{1,2},{1,3},{2,3},{2,4},{3,4}}和
w({1,2}):=01,
w({1,3}):=04,
w({2,3}):=10,
w({2,4}):=03,
w({3,4}):=09.
假设Prim和Dijkstra从节点1开始。 然后，边{1,2},{2,3},{3,4}构成唯一确定的最小生成树T ，其由Prim在序列1,2,4,3 。
路径{1,2}是从1到2的唯一最短路径， {1,3}是从1到3的唯一最短路径; {1,2}{2,4}是从1到4的唯一最短路径， {4,2}{2,1}{1,3}是从4到3的唯一最短路径。 此外， {2,3}是从2到3的唯一最短路径， {2,1}{1,4}是从2到4的唯一最短路径。 总的来说， G拥有上面的属性1和2。
Dijkstra的选择可以如下完成，其中++表示无穷大。
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
总的来说，所选节点的序列是1,2,3,4 ，这与Prim生成的序列不同。
我同意科多尔的观点，即陈述I不一定是真实的，陈述II是真实的。 Codor对语句I和II的证明是正确的。 但是，我认为陈述III并不一定是真实的，陈述IV是正确的。
对于陈述III，有一个反例：有3个顶点A，B和C.有3个边（A，B），（B，C）和（A，C），其权重分别为1,2和3 。 最小生成树包括边（A，B）和（B，C）。 然而，A和C之间的最短路径并不是唯一的：（i）（A，B），（B，C）或（ii）（A，C）
声明四是正确的。 这可以通过数学归纳来证明。
链接地址: http://www.djcxy.com/p/35221.html