最小生成树和最短路径

2018-06-12 07:48:23

我有一个问题说：

给定一个具有整数权重的连通有向图（包括正数和负数），开发一种算法，找到两个顶点之间的最短路径。

我以为我可以使用最小生成树算法，如秩的，然后使用也许Dijkstra算法表明，由于在MST，每个顶点只有一个进来的边缘，Dijkstra算法甚至会负权重的工作。

这听起来是多色的吗？

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

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

其次，通常Dikstra不会使用负权重的图表。

口渴，贝尔曼 - 福特算法可用于在有向负权重图中寻找最短路径。

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

那是因为它是错误的。采用边缘权重为2,3和4的三角形图.MST只包含权重2和3的边，但最短路径的权重为4，通过MST的路径的权重为5。

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

链接地址: http://www.djcxy.com/p/35263.html

上一篇: Minimum spanning tree and shortest path

下一篇: Differences between Minimum Spanning Tree and Shortest Path Tree