# Prim's minimal spanning algorithm

Is there a way to speed up this code so it is $O(n^2)$ instead of $O(n^3)$? I'd appreciate if someone showed me how to do so.

public void minimalSpanning(int sVertex)
{
source = sVertex;

boolean[] mstv = new boolean[maxSize];

for (int j = 0; j < gSize; j++)
{
mstv[j] = false;
edges[j] = source;
edgeWeights[j] = weights[source][j];
}

mstv[source] = true;
edgeWeights[source] = 0;

for (int i = 0; i < gSize - 1; i++)
{
double minWeight = Integer.MAX_VALUE;
int startVertex = 0;
int endVertex = 0;

for (int j = 0; j < gSize; j++)
if (mstv[j])
for (int k = 0; k < gSize; k++)
if (!mstv[k] && weights[j][k] < minWeight)
{
endVertex = k;
startVertex = j;
minWeight = weights[j][k];
}
mstv[endVertex] = true;
edges[endVertex] = startVertex;
edgeWeights[endVertex] = minWeight;
} //end for
} //end minimalSpanning


Just some points:

1. Naming:

What does mstv mean? I assumed that ms in mstv stands for minimal spanning, but what is tv then? Television?

Try clearing that up with a more "reasonable" name.

This is definitely prone to bugs:

    for (int j = 0; j < gSize; j++)
if (mstv[j])
for (int k = 0; k < gSize; k++)
if (!mstv[k] && weights[j][k] < minWeight)
{
endVertex = k;
startVertex = j;
minWeight = weights[j][k];
}


Even though there might be no bugs in the code above, accidental mistakes do occur more if you lack braces.

for (int j = 0; j < gSize; j++) {
if (mstv[j]) {
for (int k = 0; k < gSize; k++) {
if (!mstv[k] && weights[j][k] < minWeight) {
endVertex = k;
startVertex = j;
minWeight = weights[j][k];
}
}
}
}


(Note that this is using my coding habits; you may move the braces where you are comfortable with)