1
$\begingroup$

Will local best choice will lead to global best choice? In other words, I'm thinking about whether it's possible that the MST has to put its branch location in the middle of two far nodes A,B and thus would make the path from root to A and B respectively not the global minimum?


This is Prim's algorithm, at page 634 (655 is pdf reader page):

While this is Dijkstra, at page 658 (679 is pdf reader page):

Book: Introduction to Algorithm 3ed.

$\endgroup$
1
$\begingroup$

No, the MST may not find the shortest path for each pair of nodes $(r,v)$.

For example, consider a graph of three vertices $A,B,C$ with edge weight $AB\mapsto 2, AC\mapsto 2, BC\mapsto 3$. Its MST is edges AB and AC. However, the shortest path between $B$ and $C$ is the edge BC.

$\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.