Vés al contingut

Algorisme de Dijkstra

De la Viquipèdia, l'enciclopèdia lliure
Aquesta és una versió anterior d'aquesta pàgina, de data 09:33, 9 oct 2016 amb l'última edició de Joutbis (discussió | contribucions). Pot tenir inexactituds o contingut no apropiat no present en la versió actual.
Execució de l'algorisme de Dijkstra

L'algorisme de Dijkstra, també anomenat algorisme de camins mínims, és un algorisme per a la determinació del camí més curt donat un vèrtex origen a la resta de vèrtexs en un graf dirigit i amb pesos a cada aresta. El seu nom serà el Edsger Dijkstra, qui el va descriure per primera vegada el 1959.

La idea subjacent en aquest algorisme consisteix a anar explorant tots els camins més curts que parteixen del vèrtex origen i que porten a tots els altres vèrtexs, quan s'obté el camí més curt des del vèrtex origen, a la resta de vèrtexs que formen el graf, l'algorisme s'atura. L'algorisme és una especialització de la cerca de cost uniforme, i com a tal, no funciona en grafs amb arestes de cost negatiu (l'hora de triar sempre el node amb distància menor, poden quedar exclosos de la cerca nodes que en properes iteracions baixarien el cost general del camí al passar per una aresta amb cost negatiu).

Algorisme

Tenint un graf dirigit ponderat de N nodes no aïllats, sigui X el node inicial, un vector D de mida N contindrà al final de l'algorisme les distàncies des de X a la resta dels nodes.

  1. Inicialitzar totes les distàncies en D amb un valor infinit (o màxim), ja que són desconegudes al principi, exceptuant la de X que s'ha de posar a 0 (ja que la distància de X a X és 0).
  2. Sigui a = X ( a serà el node actual).
  3. Recorrem tots els nodes adjacents de a, excepte els nodes marcats com a visitats, anomenarem a aquests vi.
  4. Si la distància des de X fins v i guardada a D és més gran que la distància des de X fins a sumada a la distància des de a fins v i , aquesta se substitueix amb la segona nomenada, és a dir:
    si (Di>Da+d (a, vi)) llavors Di = Da+d (a, vi)
  5. Marquem com a visitats el node a .
  6. Prenem com a pròxim node actual el de menys valor en D (pot fer-se emmagatzemant els valors en una cua de prioritat) i tornem al pas 3 mentre existeixin nodes no visitats.

Un cop acabat l'algorisme, D estarà completament ple.

Complexitat

Ordre de complexitat de l'algorisme: O (| V | 2 +|E|) = O (| V | 2 ) sense utilitzar cua de prioritat, O ((| L |+| V |) log| V |) utilitzant cua de prioritat (per exemple un turó).

Podem estimar la complexitat computacional de l'algorisme de Dijkstra (en termes de sumes i comparacions). L'algorisme realitza al més n-1 iteracions, ja que en cada iteració s'afegeix un vèrtex al conjunt distingit. Per estimar el nombre total d'operacions només cal estimar el nombre d'operacions que es duen a terme en cada iteració. Podem identificar el vèrtex amb la menor etiqueta entre els que no estan a S k realitzant n-1 comparacions o menys. Després fem una suma i una comparació per actualitzar l'etiqueta de cada un dels vèrtexs que no estan a S k . Per tant, en cada iteració es fan com a molt 2 (n-1) operacions, ja que no pot haver més de n-1 etiquetes per actualitzar a cada iteració. Com que no es realitzen més de n-1 iteracions, cadascuna de les quals suposa al més 2 (n-1) operacions, arribem al següent teorema.

TEOREMA:  L'Algorisme de Dijkstra realitza O (n  2 ) operacions (sumes i comparacions) per determinar la longitud del camí més curt entre dos vèrtexs d'un graf ponderat simple, connex i no dirigit amb n vèrtexs.

Pseudocodi

Dijkstra (Graf G, node_font s )
for  o ∈ V [G]  do 
distància [ o ] = INFINIT
pare [ o ] = NULL
distància [ s ] = 0
Encolar (cua, graf)
mentre cua no és buida do 
o = extraer_minimo (cua)
for  v ∈ adjacència [ o ] do 
if distància [ v ]> distància [ o ]+pes (u, v) do 
distància [ v ] = distància [ o ]+pes (u, v)
pare [ v ] = o 

Una altra versió en pseudocodi sense cua de prioritat

funció Dijkstra (Graf G, node_sortida s)
// farem servir un vector per a guardar les distàncies del node sortida a la resta
int distància[n] // inicialitzats el vector amb distàncies inicials
bool vist[n] // vector de booleans per controlar els vèrtexs dels que ja tenim la distància mínima
per a cada w ∈ V [G] fer
si (no hi ha aresta entre ells i w) llavors 
distància[w] = Infinit // pots marcar la casella amb un -1 per exemple
sinó
distància[w] = pes(s, w)
fsi
fper
distància[s] = 0
vist[s] = cert
// n és el nombre de vèrtexs que té el Graf
mentre (quedin nodes per visitar) fer
vèrtex = agafar el mínim del vector distància i que no estigui visitat;
vist[vèrtex] = cert;
per a cada w ∈ successors(G, vèrtex) fer
si distància[w] > distància[vèrtex] + pes(vèrtex, w) llavors
distància[w] = distància[vèrtex] + pes(vèrtex, w)
fsi
fper
fmentre
ffunció

Al final tenim en el vector distància en cada posició la distància mínima del ertex sortida a un altre ertex qualsevol.

Implementació

#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;

int destí, origen, vèrtexs = 0;
int * costos = NULL;
 
void Dijkstra (int vèrtexs, int origen, int destinació, int * costos){
 int i, v, cont = 0;
 int * ant, * tmp;
 int * z;/* vèrtexs per als quals es coneix el camí mínim */
 double min;
 double * dist = new double [vèrtexs];/* vector amb els costos de dos camins */
 
 /* Aloc les línies de la matriu */
 ant = new int [vèrtexs];
 tmp = new int [vèrtexs];
 z = new int [vèrtexs];
 
 for (i = 0; i <vèrtexs; i++){
 if (costos [(origen - 1) * vèrtexs+i] ! =- 1){
 ant [i] = origen - 1;
 dist [i] = costos [(origen-1) * vèrtexs+i];
 }
 else{
 ant [i] = -1;
 dist [i] = HUGE_VAL;
 }
 z [i] = 0;
 }
 z [origen-1] = 1;
 dist [origen-1] = 0;
 
 /* Bucle principal */
 do{
 
 /* Trobant el vèrtex que ha d'entrar a z */
 min = HUGE_VAL;
 for (i = 0; i <vèrtexs; i++)
 if (! z [i])
 if (dist [i]> = 0 & & dist [i] <min){
 min = dist [i]; v = i;
 }
 
 /* Calculant les distàncies dels nodes veïns de z */
 if (min ! = HUGE_VAL & & v ! = destinació - 1){
 z [v] = 1;
 for (i = 0; i <vèrtexs; i++)
 if (! z [i]){
 if (costos [v * vèrtexs+i] ! = -1 & & dist [v]+costos [v * vèrtexs+i] <dist [i]){
 dist [i] = dist [v]+costos [v * vèrtexs+i];
 ant [i] = v;
 }
 }
 }
 
 }While (v ! = destinació - 1 & & mín ! = HUGE_VAL);
 
 /* Mostra el resultat de la cerca */
 cout << "\tde" <<origen << "per a" <<destí << "\t";
 if (min == HUGE_VAL){
 cout << "No Existeix\n";
 cout << "\tCost:\t-\n";
 }
 else{
 i = destí;
 i = ant [i-1];
 while (i ! = -1){
 //Printf ("<-% d ", i+1);
 tmp [cont] = i+1;
 cont++;
 i = ant [i];
 }
 
 for (i = cont; i> 0; i -){
 cout <<tmp [i-1] << "-->";
 }
 cout <<destinació;
 
 cout << "\n\tCost:" <<dist [destinació-1] << "\n";
 }
 
 delete (dist);
 delete (ant);
 delete (tmp);
 delete (z);
}
 
int menu (void){
int opció;
 cout << "Implementació de l'Algorisme de Dijkstra\n";
 cout << "Menu:\n";
 cout << ">> 1. Crear el graf\n>> 2. Determinar el menor camí del graf\n>> 0. Sortir del programa\n";
 cout <<endl;
cout << "Opció:";
cin>> opció;
while (opció <0||opcio> 2){
cout << "Opció Invalida. Digitela novament:";
cin>> opció;
}
return opció;
}
 
void add (void){
 
 
 do{
 cout << "\nIntrodueixi el nombre de vèrtexs (no mínim de 2):";
 cin>> vèrtexs;
 }While (vèrtexs <2);
 
 if (! costos)
 delete (costos);
 
 costos = new int [vèrtexs * vèrtexs];
 
 
 for (int i = 0; i <= vèrtexs * vèrtexs; i++)
 costos [i] = -1;
 
 cout << "N º Vertices =" <<vèrtexs <<endl;
 cout << "Ara unim els vèrtexs:\n";
 
 bool segueixo = true;
 
 int origen;
 int destinació;
 
 while (segueixo){
 cout << "Escolliu el primer vèrtex de l'aresta:" <<endl;
 do{
 cin>> origen;
 
 if (origen> vertices){
 cout << "El nombre del vèrtex ha de ser menor de" <<vèrtexs <<endl;
 }
 }while (origen> vertices);
 
 
 cout << "Escolliu el segon vèrtex de l'aresta:" <<endl;
 do{
 cin>> destinació;
 
if (destinació> vertices){
cout << "El nombre de vèrtex ha de ser menor de" <<vèrtexs <<endl;
}
}while (destinació> vertices);
 
int pes = 0;
cout << "Pes:" <<endl;
cin>> pes;
 
costos [(origen-1) * vèrtexs+destinació - 1] = pes;
 costos [(destinació-1) * vèrtexs+origen - 1] = pes;
 
 
int seguir = 1;
cout << "Voleu afegir una altra aresta? (0 - NO, 1 - SI, per defecte 1):";
cin>> seguir;
segueixo = (seguir == 1);
 }
 
}
 
void cercar (void){
 int i, j;
 
 cout << "Llista dels Menors Camins a Graf Atès:\n";
 
 for (i = 1; i <= vèrtexs; i++){
 for (j = 1; j <= vèrtexs; j++)
 Dijkstra (vèrtexs, i, j, costos);
 cout <<endl;
 }
 
 cout << "<Premeu ENTER per tornar al menú principal.\n";
 
}
 
int main (int argc, char ** argv){
 int opció;
 
 do{
opcion = menu ();
switch (opció){
case 1:
add ();
break;
case 2:
cercar ();
break;
}
 
 }While (opció ! = 0);
delete (costos);

 cout << "\nFins la proxima ...\n\n";
 system ( "pause");
 
 return 0;
}

C++mitjançant Heaps

Una altra possible implementació de l'algorisme de Dijkstra és mitjançant monticles binaris.

struct T_Heap{
 A turo;
 int num_elem;
};

void CrearHeap (T_Heap & heap){
 heap.num_elem = 0;
 for (int i = 0; i <MAX_HEAP; i++){
 heap.monticulo [i] = NULL;
 }//for
}
void Intercanviar (T_Heap & heap, int i, int j){
 T_Lista aux;
 
 aux = heap.monticulo [i];
 heap.monticulo [i] = heap.monticulo [j];
 heap.monticulo [j] = aux;
}
void Meter (T_Heap & heap, const T_Lista & elem){
 int k;
 
 k = heap.num_elem;
 heap.monticulo [k] = elem;
 while (k ! = 0||(heap.monticulo [k] --> pes> heap.monticulo [((k-1)/2)] --> pes){
 Intercanviar (heap, k, ((k-1)/2));
 k = (k-1)/2;
 }//while
 heap.num_elem++;
}
void Treure (T_Heap & heap, int & elem){
 int k;
 
 elem = heap.monticulo [0];
 heap.monticulo [0] = heap.monticulo [heap.num_elem-1];
 heap.monticulo [heap.num_elem-1] = NULL;
 heap.num_elem--;
 k = 0;
 while (k <heap.num_elem && (heap.monticulo[k]--> pes <heap.monticulo [2 * k+1] --> pes||
 heap.monticulo [k] --> pes <heap.monticulo [2 * k+2] --> pes)){
 if (heap.monticulo [k] <heap.monticulo [2 * k+1]){
 Intercanviar (heap, k, 2 * k+1);
 k = 2 * k+1;
 }else{
 Intercanviar (heap, k, 2 * k+2);
 k = 2 * k+2;
 }//if
 }//while
}
bool HeapLleno (const T_Heap & heap){
 return (heap.num_elem == MAX_HEAP);
}
bool HeapVacio (const T_Heap & heap){
 return (heap.num_elem == 0);
}
void DestruirHeap (T_Heap & heap){
 for (int i = 0; i <MAX_HEAP; i++){
 heap.monticulo [i] = NULL;
 }//for
 heap.num_elem = 0;
}

Aquesta és una implementació de l'algorisme de Dijkstra mitjançant monticles binaris, que és capaç de donar els millors resultats perquè l'algorisme de Johnson sigui més eficient. La implementació de l'algorisme retorna una matriu d'elements precedents i un altre de distàncies, mitjançant el primer es pot seguir el camí de menor cost des del node passat com a argument a qualsevol altre node del graf, i si paral·lelament anem sumant les distàncies de l'altre array, obtenim el cost total d'aquests camins mínims.

void Dijkstra (const T_Grafo & graf, int origen, T_Vector & distàncies, T_Vector & anteriors)
{
 T_Vector marcats;
 T_Heap colap;
 T_Lista aux;
 
 InicializarVector (distàncies);//inicialitza els elements a -1
 InicializarVector (anteriors);
 InicializarVector (marcats);
 distàncies [origen] = 0;
 marcats [origen] = 0;
 CrearHeap (colap);
 MeterAdyacentes (colap, graf, origen, marcats);
 while (! HeapVacio (colap){
 aux = Treure (colap);
 marcats [aux--> origen] = 0;
 MeterAdyacentes (colap, graf, aux--> origen, marcats);
 while (aux ! = NULL){
 if (distàncies [aux--> destí]> (distàncies [aux--> origen]+aux--> pes)){
 distàncies [aux--> destí] = distàncies [aux--> origen]+aux--> pes;
 pare [aux--> destí] = aux--> origen;
 }//if
 aux = aux--> seg;
 }//while
 }//while
}

Enllaços externs