I am thinking of using Prim's algorithm for optimizing a water pipeline problem. I am very much puzzled how to initialize the adjacency matrix when there is an edge with adjacent vertex found. I thought of putting weight whenever an edge exists. However, w(Vi,Vj) in itself looks to be a weight matrix. So, why do I need A{Vi,Vj} in the first place.
All i intent to do is to write an algorithmic approach, and carry on with writing a program later on. Please suggest if below is ok?
Set an adjacency matrix A{Vi,Vj}. Here Vi contains all the nodes visited and Vj contains all the adjacent nodes to Vi that are visited. Below matrix will store all the pair of houses which are connected with their neighbouring pair of houses through a certain distance. I am confused tha
for each Vi:=1 to n do //Vith is the ith vertex which stores a pair of house for each Vj:=1 to n do //Vjth is the adjacent pair of house with some weight if (edge exists between Vi and Vj) then Set A{Vi,Vj} with w(Vi,Vj) else if(edge not exists between Vi and Vj) then Set A[Vi,Vj]:=0
Calculating the minimum spanning tree.
In graph algorithms as in your question, if weights are given, usually adjacency is not explicitly encoded in addition to the weights. Instead, the graph is considered to be a complete graph (i.e. evey vertex is adjacent to any other vertex), but for non-adjacent vertices u, v in the initial graph the weight is encoded as 'infinity', encoded as the maximum value of the used data type, some negative value which is recognized in calculations or the like. Using this approach, infeasible edges will never be taken into accout as they are more expensive than any feasible solution of the initial problem.