Dijkstra Algorithm(Proof of Correctness)

[Peter_APIIT]

Hello to all expect programmer, i have developed a dijkstra algorithm but i not sure whether it meet the correctness of this algorithm. Therefore, i hope someone can give some opinion about my implementation.


template <typename T, class edgeType>
void graph<T, edgeType>::dijkstra()
{
// To store min vertex
typedef std::priority_queue<graph<T>::vertexPtr> PQ;
PQ cont;

// backtrack vertex and its distance
typedef map<string, int> myMap;
myMap backVertex;
stack<myMap> restoreStack;

// To store visited vertex
vector<vertexPtr> visitedVertex;
vector<int> distance;
vector<graph<T>::vertexPtr> result;

boost::shared_ptr<vertex<T> > aVertex;
std::vector<edgePtr> myEdge;

cont.push(allVertex[0]);
distance.push_back(0);
while (!cont.empty())
{
aVertex = cont.top();
cont.pop();

visitedVertex.push_back(aVertex);
result.push_back(aVertex);
myEdge = aVertex->getIncidentEdge();

string minVertexID("");
int minWeightage = myEdge[0]->getWeightage();
for (int counter=0;counter<static_cast<int>(myEdge.size());++counter)
{
bool isNotVisit = true;
for (int sentinel=0;sentinel<static_cast<int>(visitedVertex.size());++sentinel)
{
if (visitedVertex[sentinel]->getVertexID()
== myEdge[counter]->getSecondVertexID())
{
isNotVisit = false;
if (counter + 1 < static_cast<int>(myEdge.size()))
{
minWeightage = myEdge[counter+1]->getWeightage();
minVertexID = myEdge[counter+1]->getSecondVertexID();
}
break;
}
else
{
isNotVisit = true;
}
}

if (isNotVisit)
{
if (counter + 1 < static_cast<int>(myEdge.size()))
{
// To determine min weightage
if (myEdge[counter+1]->getWeightage() < minWeightage)
{
minWeightage = myEdge[counter+1]->getWeightage();
minVertexID = myEdge[counter+1]->getSecondVertexID();
myEdge.erase(myEdge.begin()+counter+1);
}
}
}
}

// Update backtrack vertex and its distance



// push minVertexID and update its distance
for (int myLoop=0;myLoop<static_cast<int>(allVertex.size());++myLoop)
{
if (allVertex[myLoop]->getVertexID() == minVertexID)
{
cont.push(allVertex[myLoop]);
minWeightage = distance.at(distance.size()-1) + minWeightage;
distance.push_back(minWeightage);
break;
}
}

minVertexID.erase(0);
minWeightage = 0;
}

// Display result
cout << "\n\n";
for (int myLoop=0;myLoop<static_cast<int>(result.size());++myLoop)
{
cout << result[myLoop]->getVertexID()
<< "(" << distance[myLoop] << ")" << "->";
}

}




Thanks.