Minimum spanning tree and shortest path

I was given a problem that said:

given a connected directed graph with integer weights (both positive and negative), develop an algorithm that finds the shortest path between two vertices.

I thought I could use a minimum spanning tree algorithm such as kruskal's and then use maybe dijkstra's algorithm to show that since in an MST, every vertex only has one incomming edge, dijkstra's algorithm will work even with negative weights.

does this sound copasteic?

ps I'm having trouble proving that an MST contains the shortest path for a directed graph, for every vertex.

---

First, you should note that your graph should not have any negative cycle.

Second, Normally Dikstra would not work with graphs with negative weights.

Thirst, Bellman-Ford Algorithm could be used for finding shortest path in a directed with-negative-weights graph.

---

I'm having trouble proving that an MST contains the shortest path for a directed graph, for every vertex.

That's because it's false. Take a triangle graph with edge weights 2, 3, and 4. The MST contains only the edges of weight 2 and 3, but the shortest path has weight 4 and the path through the MST has weight 5.

Given this, embedding minimal spanning trees in your algorithm seems like a bad idea.

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

上一篇: 图中两个节点之间的最短路径的索赔？

下一篇: 最小生成树和最短路径