I have a complete graph G
which is directed. In essence, a node is connected to all other nodes in the graph. Also, for every pair of nodes, say v
and u
, there exists two weighted edges one from u
tov
, and another from v
to u
.
Under such a configuration for the graph, if I use prim's algorithm, will the algorithm give me an arborescence, which is minimal to the root node, though not to the graph?
I understand that a single run of the prim's algorithm need not give a minimum cost arborescence for the graph. But by finding minimal arborescence by considering each one of the node in graph as root node and then using prim's algorithm, wouldn't this give me the minimum cost aroborescence.
Since the graph G is complete, isn't it guaranteed that an arborescence exist for any given node in G? SO doesn't finding all the minimal cost arborescence for each of the rooted node using prim's and listing them would lead to finding the minimum cost arborescence
I use prim's algorithm as a search procedure for a machine learning structured predction task. So, increase in complexity is not the major concern here for the time being. Using Chu-Liu-Edmond's is not an option under our setting.