[Algoritem] Kako do najkrajše poti na med točkami

joze67 je 4. jun 2010 ob 09:27 izjavil:

Kakšen primer je to, da je O(n^3) algoritem boljši od O(n logn)?

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] << ")" <<  "->";
	}

}

napsy je 3. jun 2010 ob 23:31 izjavil:

Dijkstra, Kruskal, ...
Minimum spanning tree @ Wikipedia