0
$\begingroup$

I would like to construct a Minimum Distance Spanning Tree (Dijkstra) for the graph below:

enter image description here

MDST: {(a,c), (c,h), (c,f), (a,d), (h,g), (a,b), (d,e), (h,j), (h,i), (j,k), (e,m), (i,l)}

enter image description here

Is my understanding correct? The total cost would be 49 (sum of the distance from the root for each node).

Improve this question
$\endgroup$
1
  • $\begingroup$ I think you are confusing MST with the shortest path problem. The two most common MST algorithms are Kruskal and Prim's algorithms that already work on weighted graphs. Dijkstra algorithm, whereas calculates the shortest distance from one to all. $\endgroup$
    – kelalaka
    Dec 10, 2018 at 17:50

2 Answers 2

Reset to default
2
$\begingroup$

Like other have pointed out, it seems you are confused by the difference between a minimum spanning tree, and a shortest path tree.

A minimum spanning tree, is a tree such that it spans all vertices, and the sum of all edges is as minimum as possible.

A shortest path tree, is a rooted tree such that the distance between the root, and any other vertex is as minimum as possible. (That doesn't necessary mean that the sum of its edges has to be minimum as possible).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nitpicking: "the sum of all edges" should be "the sum of weights of all edges". $\endgroup$
    – John L.
    Dec 11, 2018 at 17:32
1
$\begingroup$

What you are computing is typically called a shortest-path tree; yours is rooted at $a$. Note that, in this example, the shortest-path tree rooted at $a$ is not unique. You could have taken the edge $(d, e)$ instead of $(a, e)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.