Algoritmo de Dijkstra

Edsger Wyde Dijkstra

Nacido en Rotterdam, (Holanda) en 1930, su padre era químico y su madre matemática. con 12 años,  entró en Gymnasium Erasminium, una escuela para estudiantes especialmente brillantes, donde dio clases de Griego, Latín, Francés, Alemán, Inglés, biología, matemáticas y química. Debido a su facilidad para la química, las matemáticas y la física, entró en la Universidad de Leiden, donde decidió estudiar física teórica. Después de asistir a un curso de programación en la Universidad de Cambridge, empezó a trabajar en el Centro Matemático en  Amsterdam, donde se incrementó su creciente interés en la programación. Cuando terminó la carrera se dedicó a problemas relacionados con la programación.  El resto de su vida se dedico a la investigación y desarrollo de diversos problemas de programación hasta su reciente muerte en el año 2002

En 1959, Dijkstra anunció su algoritmo de caminos mínimos o también llamado ruta mas corta o árbol mínimo

Algoritmo de Dijkstra

Propuesto en 1959 el algoritmo de caminos mínimos o también llamado ruta mas corta o árbol mínimo o simplemente algoritmo de Dijkstra es un algoritmo para determinar el camino o ruta mas corta desde un nodo de origen hacia los demás nodos del grafo, en el cual cada arista o arco posee un peso. Se siguen una serie de pasos y consideraciones que veremos a continuación

Pasos para su aplicacion

Para realizar la aplicación del algoritmo de  Dijkstra, se aplican los siguientes pasos:

1. Se elige un nodo de inicio al cual se le marcara un peso de la siguiente forma:

      [X,Y](N)

Donde ‘X’ equivale a el valor del recorrido actual de los arcos, ‘Y’ equivale a el nodo predecesor o de origen y ‘N’ al numero de iteración u operación actual

2. A los nodos adyacentes del nodo seleccionado como nodo de inicio, se deben asignar un peso de igual forma al punto anterior, ( [X,Y](N) )

3. De los nodos con los pesos calculados se toma el nodo con menor valor en X y este será el siguiente a visitar

4. Los pasos 2 y 3 deben repetirse teniendo en cuenta que si al intentar calcular los pesos para los nodos adyacentes a un nodo que esta siendo visitado, uno de estos ya tiene un peso asignado, deben calcularse los demás pesos cuantas veces sean necesario, y siempre se tomara el peso mínimo calculado

5. Los nodos pueden ser visitados una sola vez

VIDEOS

https://www.youtube.com/watch?v=VENf0GXRd6E

https://www.youtube.com/watch?v=LLx0QVMZVkk

Pseudocòdigo

Dijkstra (G,s)

Inicializar

    for cada v perteneciente a V[G]

        do d[v] = infinito

            p[v] = nulo

    d[s] = 0

S =  vacio

Q = V[G]

mientras Q no vacío

do u = nodo v con min d[v]

S = S unión u 'se añade al conjunto de nodos finalizados

for cada v perteneciente Adyacente u

   

        if d[v] > d[u] + w(u,v) then

            d[v] = d[u] + w(u,v)

            p(v) = u

Aplicacoines

Aplicaciones

•Encaminamiento de paquetes por routers

•Enrutamiento de Aviones y trafico aéreo

•Movilidad terrestre

•Sistemas de geolocalisacion

CODIGO C++

#include "stdio.h"

#include "conio.h"

#include "stdlib.h"

//#include "alloc.h"

#define MAXIMO 20

#define PR(x) printf ("%s",x)

#define SALTO printf ("\n")

int main() {

int M[MAXIMO][MAXIMO],T[MAXIMO][MAXIMO];

int suma, marcas[MAXIMO],padres[MAXIMO],minimo [MAXIMO];

int nv,i;

void DIJKSTRA (int M[][MAXIMO],int N,int minimo[],

int padres[],int marcas[]);

void listar_r (int a[],int nv);

int lea_grafo (int grafo[][MAXIMO]);

void listar_g (int g[][MAXIMO], int nv);

nv = lea_grafo (M);

listar_g (M ,nv);

SALTO;

getch();

DIJKSTRA (M,nv,minimo,padres,marcas);

listar_r (minimo,nv);

SALTO;

listar_r (padres,nv);

SALTO;

listar_r (marcas,nv);

SALTO;

getch();

}

void DIJKSTRA (int M[][MAXIMO],int N,int minimo[],

int padres[],int marcas[])

{

int min;

int j,k,escogido;

for (j=1; j<=N; j++ ) {

minimo[j] = M[1][j];

marcas [j] = 0;

padres [j] = 1;

}

minimo [1] = 0;

padres [1]= 0;

marcas [1] = 1;

for (k = 2; k <= N; k++) {

min = 32000; /* No puede ser 32767 para maquinas de 16 bits

para cada entero. ?Porque? */

for (j=1; j <= N; j++)

if (marcas [j] == 0 && minimo [j] < min) {

min = minimo [j];

escogido = j;

}

marcas [escogido] = 1;

for (j=1; j <= N; j++)

if (marcas [j] == 0 &&

(min + M[escogido][j] < minimo[j]) ) {

minimo [j] = min + M[escogido][j];

padres [j] = escogido;

}

}

}

int lea_grafo (int grafo[][MAXIMO])

{

int lea(),v,ad,i,j,n,costo;

PR("De numero de vertices...");

SALTO;

n = lea();

for (i=1; i <= n; i++)

for (j=1; j <=n; j++)

grafo[i][j] = 32000;

PR ("Vertice  ... ");

v = 1;

printf ("%d",v);

SALTO;

while (v <= n) {

PR ("Lea el primer adjunto al vertice ");

printf ("%d ",v);

PR(". 99 para terminar");

SALTO;

ad = lea();

while (ad != 99) {

PR("Lea costo del arco");SALTO;

costo = lea();

grafo [v][ad] = costo;

PR ("Lea otro adjunto al vertice ");

printf ("%d ",v);

PR(". 99 para terminar");

SALTO;

ad = lea();

}

PR ("Vertice ...");

v++;

printf ("%d ",v);

SALTO;

}

return (n);

}

int lea() {

char L[10];

gets (L);

return (atoi (L));

}

void listar_g (int g[][MAXIMO], int nv) {

int i,j;

for (i=1; i <= nv; i++) {

for (j = 1; j <= nv; j++)

if (g[i][j] == 32000)

printf ("%s"," * ");

else printf ("%2d ",g[i][j]);

SALTO;

}

}

void listar_r (int a[],int nv) {

int k;

for (k=1; k<=nv; k++)

printf ("%d ",a[k]);

}