Minimum spanning tree and shortest path

0
votes

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?

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

2
algorithmgraph-algorithmshortest-pathminimum-spanning-tree
Consider an n-dimensional grid for n >= 2. A MST, like any tree, has leaves with only one edge connected to them. A point on an n-dimensional grid has n adjacent points in n different directions, so the MST does not support all possible shortest paths to adjacent points. – mcdowella

2 Answers

2
votes

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.

0
votes

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.