使用Dijkstra's将2的幂返回相同的最短路径吗？

我有一个图G =（V，E），其中有两个权重函数w1（e）和w2（e），其中 w1（e）=（w2（e））^ 2。所有边缘权重都是独一无二的。使用Dijkstra's将2的幂返回相同的最短路径吗？

在两个权重函数下，Kruskal的算法将返回相同的最小生成树。

我知道kruskal是贪婪的，会选择最短/最低成本的路径。既然它们是肯定的，只要没有成本为1.5或者更低的路径，我们最终会选择相同的MST。

在两个权重函数下，Dijkstra的算法将返回相同的最短路径。

我不确定这个。我认为这也是事实，但我觉得如果我们得到足够多的数字，一条路径实际上可能会变得更大。任何人都可以证实，如果我们要幂的路径长度？

不是。想象两条路径，一条路径的权重为1 + 2 + 3，另一条的权重为4.现在计算每条边的权重。

2017-09-22 15:28:07

这是为了迪杰斯特拉的假设吗？我们可以拥有比另一个更多边缘的路径吗？我明白，以你的榜样为例，我们将有不同的最短路径，但它们似乎是两个不同的例子？ –

@Andrew Raleigh：我不明白你的问题。当然，你可以在两个节点之间有多条路径。如果只有一条路径，找到最短路径将是微不足道的。 –

我的意思是克鲁斯卡尔的算法是否符合假设？我的意思是说，你选择Djikstra的例子有4，这将是16.然后你给了另一个是1,2和3，这将是1,4和9.所以我没有真的得到你的反例如何工作，对不起：（ –

回答