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 = noeudNonVuDistanceMin();
		
		if (v == nullptr) break;
		v->vu = true;

		for (int j=0; j<(int)v->arcs.size(); j++)
		{
			Noeud* w = v->arcs[j]->dest;
			int dw = v->dv + v->arcs[j]->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;
			}
		}


	}

	for (map<string, Noeud*>::iterator itNode = noeuds.begin(); itNode != noeuds.end(); ++itNode)
	{
		cout << itNode->second->nom << " ( dv=" << itNode->second->dv << "; parent=";
		if (itNode->second->parent != nullptr)
			cout << itNode->second->parent->nom << ")" << endl;
		else
			cout << "NULL)" << endl;

	}

	return resultat;
}