algorithm - 最小生成树和最短路径

Question

我遇到了一个问题，说：

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

我想我可以使用最小生成树算法，例如 kruskal 的算法，然后使用 dijkstra 的算法来证明，因为在 MST 中，每个顶点只有一个传入边，所以即使使用负权重，dijkstra 的算法也可以工作。

这听起来像哥斯达黎加吗？

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

Answer 1

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

其次，通常 Dikstra 不适用于具有负权重的图。

Thirst，Bellman-Ford 算法可用于在有向负权重图中寻找最短路径。

Answer 2

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

那是因为它是假的。以边权重为 2、3 和 4 的三角形图为例。MST 仅包含权重为 2 和 3 的边，但最短路径的权重为 4，通过 MST 的路径的权重为 5。

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