ca Algorisme de Dijkstra

	En altres projectes de Wikimedia:
Commons	Commons (Galeria)
Commons	Commons (Categoria)

L'algorisme de Dijkstra, també anomenat algorisme de camins mínims, és un algorisme de cerca de camins per determinar el 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 li ve d'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 (a 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.

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).
Sigui a = X (a serà el node actual).
Recorrem tots els nodes adjacents de a, excepte els nodes marcats com a visitats, anomenarem a aquests v_i.
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 (D_i>D_a+d (a, v_i)) llavors D_i = D_a+d (a, v_i)
Marquem com a visitats el node a .
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 |²+|E|) = O (| V |²) 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 ²) 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

Estructura de dades auxiliar: Q = Estructura de dades Cua de prioritat (es pot implementar amb un turó)

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ó

Python

Implementació en Python de l'algorisme de Dijkstra. Els nodes i camins mostrats corresponen als del grafic il·lustratiu de l'inici de la pàgina.

El graf s'ha implementat utilitzant un diccionari per a emmagatzemar tots els nodes. Cada node compta amb un valor/identificador i un diccionari de veïns, que s'utilitza per a emmagatzemar també el cost del camí.

import math


class WeightedGraph:
 """
 Classe que implementa el graf no dirigit.
 """
 def __init__(self):
 """Constructor. Només cal un diccionari on anirem col·locant els nodes"""
 self.g = {}

 def add_node(self, node):
 """Mètode per afegir un node."""
 self.g[node] = WeightedNode(node)

 def add_edge(self, node1, node2, weight):
 """Mètode per afegir un vèrtex/camí entre dos nodes."""
 self.g[node1].add_edge(node2, weight)
 self.g[node2].add_edge(node1, weight)

 def dijkstra(self, start):
 """
 Algorisme de Dijkstra per a trobar el camí més curt des d'un node cap a tots els altres.
 """
 # Crea un diccionari on ficar la distància mínima fins a tots els nodes.
 distances = {key: math.inf for key in self.g.keys()}
 distances[start] = 0

 # Inicialitza els arrays per a saber els nodes pels que ha passat i pels que ha de passar.
 to_check = [start]
 checked = []

 # Bucle principal.
 for node in to_check:

 # Comprova tots els veïns del node en qüestió.
 for neighbor, weight in self.g[node].edges.items():

 # Si no ha estat comprovat i no està a la llista per a ser-ho,
 # s'afegeix a la llista per a ser investigat.
 if neighbor not in checked and neighbor not in to_check:
 to_check.append(neighbor)

 # Si el camí actual fins al veí en qüestió és més curt que el conegut, s'actualitza.
 if distances[neighbor] > distances[node] + weight:
 distances[neighbor] = distances[node] + weight

 # Un cop comprovats els veïns d'un node, aquest es marca com a investigat.
 checked.append(node)

 return distances

 def __str__(self):
 """Mètode per a poder visualitzar el graf en una cadena de caràcters."""
 string_nodes = []
 for node in self.g.values():
 string_nodes.append(str(node))
 return f"[{', '.join(string_nodes)}]"


class WeightedNode:
 """
 Classe que implementa el node d'un graf ponderat.
 """
 def __init__(self, value):
 """Constructor. Es necessita el valor/identificador i un diccionari pels camins."""
 self.value = value
 self.edges = {}

 def add_edge(self, node, weight):
 """Mètode per a afegir un camí ponderat a un node."""
 self.edges[node] = weight

 def __str__(self):
 """Mètode per a poder visualitzar un node en una cadena de caràcters."""
 return f"{self.value} -> {self.edges}"


if __name__ == '__main__':
 # S'instancia l'objecte WeightedGraph
 graph = WeightedGraph()

 # S'afegeixen els nodes del graf.
 graph.add_node('A')
 graph.add_node('B')
 graph.add_node('C')
 graph.add_node('D')
 graph.add_node('E')
 graph.add_node('F')

 # S'afegeixen els camins entre nodes i el seu pes.
 graph.add_edge('A', 'B', weight=7)
 graph.add_edge('A', 'C', weight=9)
 graph.add_edge('A', 'F', weight=14)
 graph.add_edge('B', 'C', weight=10)
 graph.add_edge('B', 'D', weight=15)
 graph.add_edge('C', 'D', weight=11)
 graph.add_edge('C', 'F', weight=2)
 graph.add_edge('D', 'E', weight=6)
 graph.add_edge('E', 'F', weight=9)

 print(graph)

 # Es crida la funció per a trobar els camins més curts a tots els nodes des del node 'A'.
 result = graph.dijkstra('A')
 print(result)

C++

#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;
 ist [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;
 }
}

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;
 }
 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;
 }
 }
}

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;
 }
 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;
 }
 aux = aux--> seg;
 }
 }
}

Enllaços externs

de l'Algorisme de Dijkstra
Graph mòdul Perl a CPAN
Bio:: Coordinate:: Graph mòdul Perl a CPAN que implementa l'algorisme de Dijkstra