# Algorisme de Dijkstra

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 |$^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:
   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

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

## Una altra versió en pseudocodi sense cua de prioritat

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í.

### C++ mitjançant Heaps

Una altra possible implementació de l'algorisme de Dijkstra és mitjançant monticles binaris.
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.

## 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