Clasa a XI-a lecția 27

From Algopedia
Jump to navigationJump to search

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

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_a_XI-a_lecția_27&oldid=17571"