Dijkstra algorithm problem

How to apply Dijkstra algorithm for a graph to find the MST in s开发者_运维问答uch a way that the resulting tree must have an edge between two given vertices? (ex: MST must include an edge between X and Y)

Thanks

Dijkstra's algorithm is for shortest paths (not MST), but something similar to Dijkstra's algorithm, as modified to find a minimum spanning tree, is called Prim's algorithm. Prim's algorithm keeps a tree that grows until it spans the entire graph. The additional constraint introduced here does not pose much difficulty: you just start with X-Y as your tree.

Specifically, given that your MST must include the edge (X,Y) (if there are multiple such edges pick the one of smallest weight), start with your tree having two nodes X and Y and the edge between them. Now at each step pick the smallest edge (u,v) where u is in your tree and v outside, add node v and the edge (u,v) to your tree, and repeat.