Create a MST with depth-first search?

Question

I have a symmetrical graph and created a tree with all shortest path from a random vertex to any other vertex. Can I use the tree to construct a Minimum Spanning Tree(MST)? My algorithm is similar to depth-first algorithm.

Borderline

No, because the shortest path from A to B and from A to C will not tell you the shortest path from B to C. – Aristophanes

can you explain? when you have 3 vertex mst is a-b and a-c. no need b-c? – Borderline

"mst is a-b and a-c" --- it's an "st" all right, but why is it "m"? – Shiau

why it's a-b-c? I have all shortest path. – Borderline

not sure why you freaking. my accuracy isn't so good. – Borderline

mst needs to visit all vertex. but shortest path not. there you have the information you asked me? – Borderline

"a tree with all shortest path from a random vertex to any other vertex" I think that Tyler and I both understand this to mean the rooted tree such that, for every vertex, the path that appears in the tree from the root to that vertex is a shortest path. If we forget the root, then this tree is a spanning tree, but in general, it has very little to do with the minimum spanning tree. If this still does not make sense, then you need to edit in an example with enough vertices to be interesting. – Doublebank

my shortest path tree was a minimum spanning tree. I confused vertex and edged. – Borderline

Answer 1

In the worst case, a shortest path tree does not help in finding a minimum spanning tree. Consider a graph where we want to find the MST. Add a source vertex with edges of an identical large length to each other vertex. The shortest path tree from that source consists of the very long edges, which we knew a priori, hence the shortest path tree is not useful in this case.

Doublebank

It's not answering my question. It's like @tyler comment. – Borderline

@Phpdna Suppose a-b has length 100 and a-c has length 100 and b-c has length 1. The shortest path tree rooted at a is a-b and a-c. The MST is b-c and one of the other edges. – Doublebank

but mst needs to visit all vertex. if you can merge the shortest path you have the mst. – Borderline