dikstrap

Graphe Graphe::dijkstra(const string source)
{
	Graphe resultat;

	map<string, Noeud*>::iterator itNode;


	Noeud* s = noeuds[source];

	s->dv = 0;

	for (int i = 0; i <= noeuds.size(); i++)
	{
		Noeud* v = nullptr;
		int lowestdv = INT_MAX; //On initialize lowestdv a INT_MAX

		//noeudNonVuDistanceMin() : Chercher le noeud avec vu == false et dv le plus petit
		for (itNode = noeuds.begin(); itNode != noeuds.end(); ++itNode)
		{
			

			//Si la distance de sommet source au itNode->second < lowestdv + itNode->second n'est pas vu
			//le dv de itNode devient le nouveau lowestdv et v devient le itNode->second
			if (itNode->second->dv < lowestdv && itNode->second->vu == false) {
				lowestdv = itNode->second->dv;
				v = itNode->second;
			}
				
			if (v == nullptr) break;
			v->vu = true;

			for (map<string, Arc*>::iterator itArc = v->arcs.begin(); itArc != v->arcs.end(); ++itArc)
			{
				Noeud* w = itArc->second->dest;
				int dw = v->dv + itArc->second->poids; //Distance de w = dist de v + le poids du noeud actuel
				if (w->vu == false && dw < w->dv) {
					w->dv = dw;
					w->parent = v;
				}
			}

			cout << itNode->second->nom << " ( dv=" << itNode->second->dv << "; parent=" << itNode->second->parent << ")" << endl;
		}

	}

	return resultat;
}