Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void Grafo::dijkstra(int origen)
- {
- priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
- pair<int, int> p;
- pair<int, int> aux;
- pair<int, int> adya;
- int v, i;
- vecAux[origen].setDistancia(0);
- p.first = vecAux[origen].getDistancia();
- p.second = origen;
- q.push(p);
- while (!q.empty())
- {
- i = 0;
- aux = q.top();
- q.pop();
- v = aux.second;
- if (!vecAux[v].getMarca())
- {
- vecAux[v].setMarca(true);
- adya = sacarSigAdyacente2(v, i);
- while (adya.first != -1)
- {
- if (!vecAux[adya.first].getMarca() && adya.second > 0)
- {
- if (vecAux[v].getDistancia() + adya.second < vecAux[adya.first].getDistancia())
- {
- vecAux[adya.first].setDistancia(vecAux[v].getDistancia() + adya.second);
- vecAux[adya.first].setPadre(v);
- p.first = vecAux[adya.first].getDistancia();
- p.second = adya.first;
- }
- }
- adya = sacarSigAdyacente2(v, i);
- }
- }
- }
- }
- pair<int, int> Grafo::sacarSigAdyacente2(int v, int & i)
- {
- pair<int, int> resp;
- while (mat[v][i] == 0 && i < 50)
- i++;
- if (i < 50)
- {
- resp.first = i;
- resp.second = mat[v][i];
- }
- else
- {
- resp.first = -1;
- resp.second = -1;
- }
- i++;
- return resp;
- }
- void Grafo::mostrarCamino(int origen, int destino, bool & b)
- {
- if (vecAux[destino].getPadre() != -1)
- {
- mostrarCamino(origen, vecAux[destino].getPadre(), b);
- if (b)
- cout << vecAux[destino].getPadre() << endl;
- }
- else
- {
- if (destino == origen)
- b = true;
- else
- cout << "no hay camino" << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement