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).

$\endgroup$
  • $\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 '18 at 17:50
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).

$\endgroup$
  • $\begingroup$ Nitpicking: "the sum of all edges" should be "the sum of weights of all edges". $\endgroup$ – Apass.Jack Dec 11 '18 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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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