Difference between revisions of "Clasa a XI-a lecția 27"

From Algopedia
Jump to navigationJump to search
(Created page with "= Algoritmul lui Dijkstra = Este un algoritm care '''calculeaza drumurile minime de la un nod al unui graf la toate celelalte noduri din graf'''. Grafurile pe care poate lucra...")
 
 
Line 353: Line 353:
 
* [https://www.pbinfo.ro/?pagina=probleme&id=1069 Ubuntzei] (Grea)OJI 2011, Clasele XI-XII
 
* [https://www.pbinfo.ro/?pagina=probleme&id=1069 Ubuntzei] (Grea)OJI 2011, Clasele XI-XII
 
* [https://www.pbinfo.ro/?pagina=probleme&id=630 Joc] - Reconstituire drum
 
* [https://www.pbinfo.ro/?pagina=probleme&id=630 Joc] - Reconstituire drum
 
= TEMA REZOLVARI=
 
==[https://www.pbinfo.ro/?pagina=probleme&id=588 dijkstra pbinfo]==
 
O prezentare usor de inteles:
 
https://www.youtube.com/watch?v=0EzOk73sjC8
 
<syntaxhighlight>
 
#include <cstdio>
 
 
const int NMAX = 101;      // nr maxim de noduri
 
const int inf = 1 << 30;    // infinit
 
 
FILE *fin = fopen( "dijkstra.in", "r" );
 
FILE *fout = fopen( "dijkstra.out","w" );
 
 
struct nod {
 
  int nr_nod, cost;
 
  nod *next;
 
};
 
 
int n, start;
 
int d[NMAX];      // costurile de la start la toate nodurile
 
//int t[NMAX];      // in caz ca doresc sa reconstitui si drumul
 
int s[NMAX];      // vector caracteristic, marcam ce noduri au fost selectate
 
 
int M[NMAX][NMAX];// matricea ponderilor
 
 
void read() {
 
  fscanf( fin, "%d %d", &n, &start );
 
  for( int i = 1; i <= n; i++ )
 
    for( int j = 1; j <= n; j++ )
 
      M[i][j] = inf;
 
  int x, y, cost;
 
  while ( fscanf(fin, "%d %d %d", &x, &y, &cost )!= EOF )
 
    M[x][y] = cost;
 
 
}
 
 
void dijkstra( int start ) {
 
 
  for ( int i = 1; i <= n; i++ )    // initializam toate drumurile de la start la fiecare nod
 
    d[i] = inf;
 
  d[start] = 0;                    // dist de la start la el insusi e 0
 
 
  int min, pmin = 0;                // costul minim si nodul cu costul minim pana la start
 
  for ( int i = 1; i <= n; i++ ) {
 
 
    min = inf;                      // det. nodul cel mai apropiat de nodul de start
 
    for ( int j = 1; j <= n; j++ )  // drumul acestuia nu va mai putea fi optimizat
 
      if ( d[j] < min && !s[j] )    // avand in vedere ca avem costuri mai mari catre nodurile ce ar putea fi intermediare
 
        min = d[j], pmin = j;
 
 
 
    // parcurgem lista vecinilor nodului selectat pmin
 
    // pentru a vedea daca prin acest nod se ajunge mai repede la vecinii sai, pornind din start
 
    s[pmin] = 1;                          // marcam ca si selectat nodul intermediar
 
    for(int i = 1; i <= n; i++)
 
      if ( d[i] > d[pmin] + M[pmin][i]){  // dc costul deja memorat al nodului i e mai mare decat costul prin nodul intermediar pmin
 
        d[i] = d[pmin] + M[pmin][i];      // actualizam costul in vectorul de costuri d
 
        //t[i] = pmin;                      // marcam ca precedent al nodului i , in drumul de la p la i, ca fiind pmin
 
      }
 
  }
 
}
 
 
int main() {
 
 
  read();                          // citim muchiile si costurile acestora, construind listele de adiagenta
 
  dijkstra(start);                  // calculam distantele de la nodul start la toate celelalte
 
  for ( int i = 1; i <= n; i++ )    // afisam dinstantele de la nodul start la fiecare nod
 
    fprintf(fout, "%d ", d[i] == inf ? -1 : d[i]);
 
  fprintf(fout, "\n");
 
 
  return 0;
 
}
 
 
</syntaxhighlight>
 
== [https://www.pbinfo.ro/?pagina=probleme&id=1887 Dijkstra2 pbinfo] ==
 
Problema este asemanatoare cu precedenta. Aici avem insa un graf neorientat iar intrarea difera ca forma. Observam insa ca la aceasta problema '''numarul de noduri este foarte mare''', pastrarea in memorie a unui tablou cu 10^10 elemente nefiind posibila, de asemenea si o complexitate de timp este foarte mare. Aveti mai jos prezentati 3 variante de algoritimi drept studiu comparativ:
 
* primul algoritm depaseste si memoria si timpul
 
* al doilea optimizeaza memoria folosind liste de adiacente, dar timpul de executie mare
 
* al treilea optimizeaza atat memoria prin folosirea listelor de adiacenta, dar si timpul de executie .
 
 
Daca n ar fi ca la problema precedenta algoritmul ar arata asemanator, ca in implementarea de mai jos.
 
<syntaxhighlight>
 
// algoritm identic cu cel de la problema dijkstra
 
// aici avem graf neorientat , si citirea datelor de intrare este diferita
 
// algoritmul afiseaza drumurile minime de la un nod p la toate celelalte noduri
 
// !!! Atentie n e foarte mare
 
#include <cstdio>
 
 
const int maxn = 1000;      // nr maxim de noduri (micsorat fata de cerintele problemei)
 
const int inf = 1 << 30;    // infinit
 
 
FILE *fin = fopen( "dijkstra2.in", "r" );
 
FILE *fout = fopen( "dijkstra2.out","w" );
 
 
int n, m, p;
 
int d[maxn];          // costurile de la start la toate nodurile
 
int s[maxn];         
 
//int t[maxn];        // predecesorii fiecarui nod i in drumul de la nodul de start
 
 
int M[maxn][maxn];
 
 
void read() {
 
  fscanf( fin, "%d%d%d", &n, &m, &p );
 
  for(int i = 1; i <= n; i++)
 
    for(int j = 1; j <= n; j++)
 
      M[i][j] = inf;
 
  int x, y, cost;
 
  for ( int i = 1; i <= m; i++ ) {
 
    fscanf(fin, "%d %d %d", &x, &y, &cost );  //citim arcul si costul asociat
 
    M[x][y] = M[y][x] = cost;
 
  }
 
}
 
 
void dijkstra( int start ) {
 
  // initializam toate drumurile de la start la fiecare nod
 
  // dist de la start la el insusi e 0
 
  for ( int i = 1; i <= n; i++ )
 
    d[i] = inf;
 
  d[start] = 0;
 
 
  int min, pmin = 0;    // costul minim si nodul cu costul minim pana la start
 
  for ( int i = 1; i <= n; i++ ) {
 
    // determin nodul cel mai apropiat de nodul de start
 
    min = inf;
 
    for ( int j = 1; j <= n; j++ )
 
      if ( d[j] < min && !s[j] )
 
        min = d[j], pmin = j;
 
 
 
    // parcurgem lista vecinilor nodului selectat pmin
 
    // pentru a vedea daca prin acest nod se ajunge mai repede la vecinii sai, pornind din start
 
    s[pmin] = 1;        // marcam ca si selectat nodul intermediar
 
    for(int i = 1; i <= n; i++){
 
      if ( d[i] > d[pmin] + M[pmin][i]){ // dc costul deja memorat al nodului nr_nod e mai mare decat costul prin nodul intermediar pmin
 
        d[i] = d[pmin] + M[pmin][i];      // actualizam costul in vectorul de costuri d
 
        //t[i] = pmin;
 
      }
 
    }
 
  }
 
}
 
 
int main() {
 
 
  read();                          // citim muchiile si costurile acestora, construind listele de adiagenta
 
  dijkstra( p );                    // calculam distantele de la nodul start la toate celelalte
 
  for ( int i = 1; i <= n; i++ )    // afisam dinstantele de la nodul start la fiecare nod
 
    fprintf(fout, "%d ", d[i] == inf ? -1 : d[i]);
 
  fprintf(fout, "\n");
 
 
  return 0;
 
}
 
</syntaxhighlight>
 
== Optimizarea memoriei ==
 
<syntaxhighlight>
 
#include <cstdio>
 
 
const int maxn = 100001;    // nr maxim de noduri
 
const int inf = 1 << 30;    // infinit
 
 
FILE *fin = fopen( "dijkstra2.in", "r" );
 
FILE *fout = fopen( "dijkstra2.out","w" );
 
 
struct nod {
 
  int nr_nod, cost;
 
  nod *next;
 
};
 
 
int n, m, p;
 
nod *L[maxn];
 
int d[maxn];  // costurile de la start la toate nodurile
 
int s[maxn];
 
 
// adauga la lista lui x nodul cu numarul y
 
void add( int x, int y, int cost ) {
 
  nod *c = new nod;
 
  c->nr_nod = y;
 
  c->cost = cost;
 
  c->next = L[x];  // ne legam de primul nod al listei lui x
 
  L[x] = c;
 
  c = new nod;
 
  c->nr_nod = x;
 
  c->cost = cost;
 
  c->next = L[y];  // ne legam de primul nod al listei lui y
 
  L[y] = c;
 
}
 
 
void read() {
 
  fscanf(fin, "%d %d %d", &n, &m, &p );
 
  int x, y, cost;
 
  for ( int i = 1; i <= m; i++ ) {
 
    fscanf(fin, "%d %d %d", &x, &y, &cost);  //citim arcul si costul asociat
 
    add(x, y, cost);
 
  }
 
}
 
 
void dijkstra( int start ) {
 
  // initializam toate drumurile de la start la fiecare nod
 
  // dist de la start la el insusi e 0
 
  for ( int i = 1; i <= n; i++ )
 
    d[i] = inf;
 
  d[start] = 0;
 
 
  int min, pmin = 0;    // costul minim si nodul cu costul minim pana la start
 
  for ( int i = 1; i <= n; i++ ) {
 
    // determin nodul cel mai apropiat de nodul de start
 
    min = inf;
 
    for ( int j = 1; j <= n; j++ )
 
      if ( d[j] < min && !s[j] )
 
        min = d[j], pmin = j;
 
 
    // parcurgem lista vecinilor nodului selectat pmin
 
    // pentru a vedea daca prin acest nod se ajunge mai repede la vecinii sai, pornind din start
 
    s[pmin] = 1;        // marcam ca si selectat nodul intermediar
 
    nod *c = L[pmin];
 
    while ( c ) {
 
      if ( d[ c->nr_nod ] > d[pmin] + c->cost )  // dc costul deja memorat al nodului nr_nod e mai mare decat costul prin nodul intermediar pmin
 
        d[ c->nr_nod ] = d[pmin] + c->cost;      // actualizam costul in vectorul de costuri d
 
      c = c->next;
 
    }
 
  }
 
}
 
 
int main() {
 
 
  read();            // citim muchiile si costurile acestora, construind listele de adiagenta
 
  dijkstra( p );      // calculam distantele de la nodul start la toate celelalte
 
  for ( int i = 1; i <= n; i++ )    // afisam dinstantele de la nodul start la fiecare nod
 
    fprintf(fout, "%d ", d[i] == inf ? -1 : d[i]);
 
  fprintf(fout, "\n");
 
 
  return 0;
 
}
 
</syntaxhighlight>
 
 
=== Optimizarea memoriei si a timpului de executie ===
 
<syntaxhighlight>
 
// implementare Pruteanu
 
#include <cstdio>
 
#include <vector>
 
#include <queue>
 
 
using namespace std;
 
 
const int NMAX=100002;
 
const int MMAX=250002;
 
 
const int INF=0x3f3f3f3f;
 
 
vector <pair <int,int> > G[NMAX]; //lista adiacenta
 
 
priority_queue <pair <int,int> > pq;
 
 
int dist[NMAX];
 
int viz[NMAX];
 
 
int main(){
 
    freopen("dijkstra2.in","r",stdin);
 
    freopen("dijkstra2.out","w",stdout);
 
    int n,m,src;
 
    int u,v,c;
 
    scanf("%d%d%d",&n,&m,&src);
 
    for(int i=1;i<=m;++i){
 
        scanf("%d%d%d",&u,&v,&c);
 
        G[u].push_back({v,c});
 
        G[v].push_back({u,c});
 
    }
 
 
    //init dist
 
    for(int i=1;i<=n;++i)
 
        dist[i]=INF;
 
    dist[src]=0;
 
 
    //
 
    for(int i=1;i<=n;++i)
 
        pq.push({-dist[i],i});
 
 
  while(!pq.empty()){
 
        pair <int,int> best=pq.top();
 
        pq.pop();
 
 
        u=best.second;
 
        if(viz[u])
 
            continue;
 
        viz[u]=1;
 
 
        for(int i=0;i<G[u].size();++i){
 
            v=G[u][i].first;
 
            c=G[u][i].second;
 
 
            if(dist[v]>dist[u]+c){
 
                dist[v]=dist[u]+c;
 
                pq.push({-dist[v],v});
 
            }
 
        }
 
  }
 
 
  for(int i=1;i<=n;++i){
 
        if(dist[i]==INF)
 
            dist[i]=-1;
 
        printf("%d ",dist[i]);
 
 
 
  }
 
 
    return 0;
 
}
 
</syntaxhighlight>
 

Latest revision as of 10:07, 25 March 2020

Algoritmul lui Dijkstra

Este un algoritm care calculeaza drumurile minime de la un nod al unui graf la toate celelalte noduri din graf. Grafurile pe care poate lucra algoritmul lui Dijkstra sunt, in general:

  • orientate
  • ponderate
  • conexe sau neconexe

Desigur ca algoritmul functioneaza si pe grafuri:

  • neorientate, graful neorientat fiind o particularitate a grafului orientat.
  • neponderate: daca graful este neponderat (arcele nu au costuri asociate) atunci drumul minim intre doua noduri se considera drumul alcatuit din numarul minim de arce. Putem transforma graful neponderat intr-un graf ponderat asociind fiecarui arc un cost egal cu 1.

Daca nu exista nici un drum de la nodul de start la un alt nod al grafului atunci algoritmul lui Dijkstra va raporta existenta unui drum de lungime infinita intre ele – acest rezultat indica, de fapt, lipsa oricarui drum intre cele doua noduri

Descriere algoritm

Intrare: Se citeste un graf orientat si ponderat cu N noduri si M arce si un nod de start apartinand grafului – acesta este nodul de la care se doreste aflarea drumurilor minime pana la celelalte noduri din graf.

Iesire: Se vor afisa distantele minime de la nodul de start la toate celelalte noduri, distante pe care le vom memora intr-un vector D cu N intrari, De asemenea, tot ca rezultat se poate obtine si arborele drumurilor minime (in cazul in care ne intereseaza nu numai lungimile minime ale drumurilor, ci si drumurile propriu-zise) – acesta este un arbore generalizat care se va obtine sub forma unui tablou T cu N intrari (implementarea cu indicatori spre parinte)

Descriere:

  • Fie X nodul de start – acesta se marcheaza ca vizitat

Ideea gasirii drumului minim de la X la un un alt nod este cautarea treptata: se presupune ca drumul minim este alcatuit dintr-un singur arc (arcul direct intre X si nodul tinta, care poate sa nu existe, costul sau fiind infinit in acest caz), apoi se cauta drumuri mai scurte alcatuite din 2 arce, apoi din 3, etc. – un drum minim nu poate avea mai mult de N-1 arce, deci algoritmul are N-1 pasi (al N-lea este banal)

  • Dupa pasul k (1 ≤ k ≤ N-1), tabloul D va contine lungimile drumurilor minime de la nodul X la celelalte noduri, toate aceste drumuri fiind alcatuite din maxim k arce
  • Astfel, D[Y] = L dupa pasul k inseamna ca de la X la Y exista un drum minim de lungime L alcatuit din maxim k arce
  • Deci, dupa pasul k, au fost gasite numai drumurile minime alcatuite din maxim k arce – abia la finalul algoritmului (dupa pasul N-1) drumurile minime obtinute sunt definitive, ele fiind drumuri minime alcatuite din maxim N-1 arce

Implementare

Afisarea costurilor drumurilor minime

dijkstra infoarena

Cu matrice de adiacenta - complexitate n*n

Complexitate O(n^2) memorie, timp

#include <cstdio>

const int maxn = 5001;     // nr maxim de noduri
const int inf = 1 << 30;   // infinit

FILE *fin = fopen( "dijkstra.in", "r" );
FILE *fout = fopen( "dijkstra.out","w" );

int n, m;
int d[maxn]; // costurile de la start la toate nodurile
int s[maxn]; // marchez nodurile selectate (nodurile pentru care am gasit deja drumul minim)
//int t[maxn]; // predecesorii fiecarui nod i in drumul de la nodul de start 
int M[maxn][maxn];

void read() {
  fscanf(fin, "%d %d", &n, &m);
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
      M[i][j] = inf;
  int x, y, cost;
  for ( int i = 1; i <= m; i++ ) {
    fscanf(fin, "%d %d %d", &x, &y, &cost );  // citim arcul si costul asociat
    M[x][y] = cost;
  }
}

void dijkstra( int start ) {  
  
  for ( int i = 1; i <= n; i++ ) // initializam toate drumurile de la start la fiecare nod
    d[i] = inf;                   
  d[start] = 0;                  // dist de la start la el insusi e 0  

  int min, pmin = 0;    // costul minim si nodul cu costul minim pana la start
  for ( int i = 1; i <= n; i++ ) {
    
    min = inf;                   // determin nodul cel mai apropiat de nodul de start
    for ( int j = 1; j <= n; j++ )
      if ( d[j] < min && !s[j] )
        min = d[j], pmin = j;


    // parcurgem lista vecinilor nodului selectat pmin
    // pentru a vedea daca prin acest nod se ajunge mai repede la vecinii sai, pornind din start
    s[pmin] = 1;         // marcam ca si selectat nodul intermediar
    for(int i = 1; i <= n; i++){
      if ( d[i] > d[pmin] + M[pmin][i]){ // dc costul deja memorat al nodului nr_nod e mai mare decat costul prin nodul intermediar pmin
        d[i] = d[pmin] + M[pmin][i];      // actualizam costul in vectorul de costuri d
        //t[i] = pmin;
      }
    }
  }
}

int main() {

  read();                     // citim muchiile si costurile acestora, construind listele de adiagenta
  int start = 1;              // fixam nodul de pornire 1
  dijkstra(start);            // calculam distantele de la nodul start la toate celelalte
  for ( int i = 1; i <= n; i++ )    // afisam dinstantele de la nodul start la fiecare nod
    if( i != start )
    fprintf(fout, "%d ", d[i] == inf ? 0 : d[i]);
  fprintf(fout, "\n");

  return 0;
}

Cu liste de adiacenta

- complexitate de Timp (n^2), de memorie O(m)

#include <cstdio>

const int maxn = 50001;    // nr maxim de noduri
const int inf = 1 << 30;   // infinit

FILE *fin = fopen( "dijkstra.in", "r" );
FILE *fout = fopen( "dijkstra.out","w" );

struct nod {
  int nr_nod, cost;
  nod *next;
};

int n, m;
nod *L[maxn];
int d[maxn];   // costurile de la start la toate nodurile
int s[maxn];

// adauga la lista lui x nodul cu numarul y
void add(int x, int y, int cost) {
  nod *c = new nod;
  c->nr_nod = y;
  c->cost = cost;
  c->next = L[x];  // ne legam de primul nod al listei lui x
  L[x] = c;
}

void read() {
  fscanf(fin, "%d %d", &n, &m);
  int x, y, z;
  for ( int i = 1; i <= m; i++ ) {
    fscanf(fin, "%d %d %d", &x, &y, &z);  //citim arcul si costul asociat
    add(x, y, z);
  }
}

void dijkstra( int start ) {
  // initializam toate drumurile de la start la fiecare nod
  // dist de la start la el insusi e 0
  for ( int i = 1; i <= n; i++ )
    d[i] = inf;
  d[start] = 0;
  
  int min, pmin = 0;    // costul minim si nodul cu costul minim pana la start
  for ( int i = 1; i <= n; i++ ) {
    // determin nodul cel mai apropiat de nodul de start
    min = inf;
    for ( int j = 1; j <= n; j++ )
      if ( d[j] < min && !s[j] )
        min = d[j], pmin = j;

    
    // parcurgem lista vecinilor nodului selectat pmin
    // pentru a vedea daca prin acest nod se ajunge mai repede la vecinii sai, pornind din start
    s[pmin] = 1;         // marcam ca si selectat nodul intermediar
    nod *t = L[pmin];
    while ( t ) {
      if ( d[ t->nr_nod ] > d[pmin] + t->cost )  // dc costul deja memorat al nodului nr_nod e mai mare decat costul prin nodul intermediar pmin
        d[ t->nr_nod ] = d[pmin] + t->cost;      // actualizam costul in vectorul de costuri d
      t = t->next;
    }

  }
}

int main() {

  read();             // citim muchiile si costurile acestora, construind listele de adiagenta
  int start = 1;      // fixam nodul de pornire 1
  dijkstra(start);    // calculam distantele de la nodul start la toate celelalte
  for ( int i = 1; i <= n; i++ )    // afisam dinstantele de la nodul start la fiecare nod
    if( i != start )
    fprintf(fout, "%d ", d[i] == inf ? 0 : d[i]);
  fprintf(fout, "\n");

  return 0;
}

Afisarea costurilor drumurilor minime RECONSTITUIRE DRUM

Mai jos aveti implementare cu matrice de adiacenta, similar poate fi implementat algoritmul folosind liste de adiacenta

// Complexitate O(n^2) memorie, timp
// Afisare drumuri de la 2 la fiecare nod.
// Atentie! Solutia nu este unica. Pot exista mai multe drumuri de cost minim 
#include <cstdio>

const int maxn = 5001;     // nr maxim de noduri
const int inf = 1 << 30;   // infinit

FILE *fin = fopen( "dijkstra.in", "r" );
FILE *fout = fopen( "dijkstra.out","w" );

int n, m;
int d[maxn]; // costurile de la start la toate nodurile
int s[maxn]; // marchez nodurile selectate (nodurile pentru care am gasit deja drumul minim)
int t[maxn]; // predecesorii fiecarui nod i in drumul de la nodul de start
int M[maxn][maxn];

void read() {
  fscanf( fin, "%d %d", &n, &m );
  for( int i = 1; i <= n; i++ )
    for( int j = 1; j <= n; j++ )
      M[i][j] = inf;
  int x, y, cost;
  for ( int i = 1; i <= m; i++ ) {
    fscanf(fin, "%d %d %d", &x, &y, &cost );  // citim arcul si costul asociat
    M[x][y] = cost;
  }
}

void dijkstra( int start ) {

  for ( int i = 1; i <= n; i++ ) // initializam toate drumurile de la start la fiecare nod
    d[i] = inf;
  d[start] = 0;                  // dist de la start la el insusi e 0

  int min, pmin = 0;    // costul minim si nodul cu costul minim pana la start
  for ( int i = 1; i <= n; i++ ) {

    min = inf;                   // determin nodul cel mai apropiat de nodul de start
    for ( int j = 1; j <= n; j++ )
      if ( d[j] < min && !s[j] )
        min = d[j], pmin = j;


    // parcurgem lista vecinilor nodului selectat pmin
    // pentru a vedea daca prin acest nod se ajunge mai repede la vecinii sai, pornind din start
    s[pmin] = 1;         // marcam ca si selectat nodul intermediar
    for(int i = 1; i <= n; i++){
      if ( d[i] > d[pmin] + M[pmin][i]){ // dc costul deja memorat al nodului nr_nod e mai mare decat costul prin nodul intermediar pmin
        d[i] = d[pmin] + M[pmin][i];      // actualizam costul in vectorul de costuri d
        t[i] = pmin;
      }
    }
  }
}
void afisare_drum( int i ){
  if( t[i] )
    afisare_drum ( t[i] );
  fprintf(fout, "%d ", i );

}
int main() {

  read();                     // citim muchiile si costurile acestora, construind listele de adiagenta
  int start = 1;              // fixam nodul de pornire 1
  dijkstra(start);            // calculam distantele de la nodul start la toate celelalte
  for ( int i = 1; i <= n; i++ )    // afisam dinstantele de la nodul start la fiecare nod
    if( i != start ){
      afisare_drum( i );
      fprintf( fout, "\n" );
    }
  fprintf(fout, "\n");

  return 0;
}

Acest algoritm presupune calcularea distantei minime de la un nod la toate celelalte noduri. Acest algoritm merge atat pe grafuri orientate, cat si pe cele neorientate. Rezolvarea acestui algoritm aduce in vedere utilizarea unei structuri noi numita priority queue, care sorteaza elementele dintr-un vector dupa anumite criterii la fiecare adaugare a unui element nou. Astfel, aceasta structura va avea doua elemente, prima care reprezinta distanta minima pentru a ajunge la nodul curent, ia a doua reprezentand nodul curent. Elementele din vectorul folosit vor fi sortate dupa prima componenta, adica dupa distanta minima pana la nodul curent. Distantele finale se vor retine intr-un vector numit rasp_dist; La fiecare pas se vor lua doua vaiabile, c_nod si c_dist, reprzentand nodul curent si distanta pana la nodul curent. Se va verifica daca valoarea lui c_dist este mai mica sau egala cu valoarea lui rasp_dist[c_nod]. Daca da, se vor lua toti vecinii lui c_nod si sse va verifica daca c_dist+distanta de la nodul curent la nodul vecin<rap_dist[nodul vecin]. Daca da, semodifica rasp_dist si se adauga in vector noul element. Procesul se repeta cat tim exista elemente in vector.

#include <bits/stdc++.h>
#include <algorithm>
 
using namespace std;
 
const int nmax=50005;
const int lim=100000000;
 
int n, m;
 
priority_queue < pair <int, int>, vector < pair <int, int> >, greater < pair <int, int> > > heap;//vectorul in care se retin nodurile si distantele, dupa cod explicarea sintaxei
vector < pair <int, int> > graph[nmax];//graful
int dist[nmax];//vectorul de raspunsuri
 
void dijkstra(int start_node)
{
    //initial toate distantele au valoarea infinit
    for(int i=1;i<=n;i++)
        dist[i]=lim;
    //e clar ca distanta fata de nodul de inceput este 0
    dist[start_node]=0;
    heap.push(make_pair(0, start_node));
    //se adauga mereu distanta prima, deoarece elementele vectorului se sorteaza dupa prima celula a perechii
    while(heap.size()>0)
    {
        int nod=heap.top().second;//nodul curent
        int cost=heap.top().first;//distanta curenta
        heap.pop();
        if(cost<=dist[nod])
        {
            for(int i=0;i<graph[nod].size();i++)
            {
                int nod_l=graph[nod][i].first;//nodul vecin
                int cost_l=graph[nod][i].second;//distanta pana la nodul vecin
                if(dist[nod_l]>cost+cost_l)//distanta curenta + distanta pana la vecin
                {
                    dist[nod_l]=cost+cost_l;//modificarea vectorului de raspunsuri
                    heap.push(make_pair(dist[nod_l], nod_l));//adaugarea unui element nou in vetctor
                }
            }
        }
    }
}
 
int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
   
    //citirea variabilelor
    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        graph[a].push_back(make_pair(b, c));
    }
    //apelarea fuctiei care retine distanta minima de la nodul 1 la celelalte noduri
    dijkstra(1);
    //afisarea distantelor
    for(int i=2;i<=n;i++)
    {
        if(dist[i]==lim)
            printf("0 ");
        else
            printf("%d ", dist[i]);
    }
    printf("\n");
 
    return 0;
}

Sintaxa de priority_queue: priority_queue < pair <int, int>, vector < pair <int, int> >, greater < pair <int, int> > > heap;

Prima celula reprezinta tipul de elemente din cadrul sructurii utilizate. Acestea pot fi int, long long, pair<> etc.; A doua celula reprezinta structura utilizata. Aceasta poate fi vector, struct etc.; A treia celula e optionala. In cazul in care vrei elementele sortate crescator, se scrie greater<prima celula folosita>. Altfel, nu se scrie nimic si se sorteaza elementele in ordine descrescatoare;

TEMA