最小生成树和最短路径

我被赋予一个问题，即表示：最小生成树和最短路径

给予连接有向图具有整数权重（正面和负面），开发发现两个顶点之间的最短路径的算法。

我以为我可以使用最小生成树算法，如kruskal的，然后使用012jxstra的算法来表明，因为在一个MST中，每个顶点只有一个包含边缘，dijkstra的算法即使在负权重下也能工作。

这听起来copasteic？

p.s.我无法证明MST包含有向图的最短路径，每个顶点都有。

2012-11-08 Jake B

考虑n> = 2的n维网格。与任何树一样，MST的叶子只有一条边连接到它们。 n维网格上的一个点在n个不同方向上有n个相邻点，因此MST不支持到相邻点的所有可能的最短路径。 – mcdowella

首先，你应该注意你的图表不应该有任何负循环。

二，通常Dikstra不会使用负权重图。

渴求，Bellman-Ford Algorithm可以用于寻找有向负权图的最短路径。

2012-11-08 03:41:35

最小生成树的规定之一没有圆圈。克鲁斯卡尔的算法证明了这一点。但是，感谢链接 –

您可以使用Bellman-ford算法，而无需创建MST。我想这将是更快的解决方案 –

@ReCoNciLiaTiOn你混淆了初始图形，也可能有负循环，以及你想要生成的生成树，这是一棵树，因此没有循环。 –

我无法证明MST包含有向图的最短路径，对于每个顶点。

这是因为它是错误的。以边权为2,3和4的三角形图.MST仅包含权重2和3的边，但最短路径具有权重4，并且通过MST的路径具有权重5.

鉴于此，在算法中嵌入最小生成树似乎是一个坏主意。

2012-11-09 19:55:40 eh9

回答