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
B and thus would make the path from root to
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.