Given a connected, directed and weighted graph, Prim's algorithm may not necessarily generate the minimal spanning tree. Suppose we have such a graph $G$ with the special condition that for every pair of vertices $x, y \in G$ there exists a directed edge from $y \to x$ and a directed edge from $x \to y$ of equal weight. I was wondering if Prim's algorithm necessarily generates a minimal spanning tree if applied to $G$?
Further, suppose that we require a hamiltonian path of minimal weight between two vertices $x, y \in G$. Would the spanning tree generated by Prim's algorithm necessarily be less than or equal to the weight of this hamiltonian path?
Best Answer
So, in your directed graph, there is an edge from 'x' to 'y' of weight 'a' iff there is an edge from 'y' to 'x' of weight 'a'. Call this graph 'G1'.
Convert 'G1' into an undirected graph 'G2' so that there is an edge from 'x' to 'y' of weight 'a' in G2 iff there is an edge from 'x' to 'y' of weight 'a' in G1.
The cost of a minimum spanning tree (MST) in G1 is necessarily equal to the cost of an MST in G2.
So, take G1 as input, convert it into G2 and feed it into Prim's algorithm. IT generates a MST on G1.
As for the second part of your Q, yes-- Prim's algorithm necessarily be less than or equal to the weight of that Hamiltonian path. If it weren't, i.e. if the Hamiltonian path is of less cost than the tree, the Hamiltonian path would be the MST itself since a simple path is also a tree. A contradiction.