Algoritmo de Dijkstra

De Wikipedia, la enciclopedia libre

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo dirigido y con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

Tabla de contenidos

1 Algoritmo
- 1.1 Complejidad
2 Pseudocódigo
3 Otra version en pseudocodigo SIN COLA DE PRIORIDAD
4 Implementación
5 Enlaces externos

[editar] Algoritmo

Sea G=(V,A) un grafo dirigido y etiquetado.
Sean los vértices a ∈ V y z ∈ V; a es el vértice de origen y z el vértice de destino.
Sea un conjunto C ⊂ V, que contiene los vértices de V cuyo camino más corto desde a todavía no se conoce.
Sea un vector D, con tantas dimensiones como elementos tiene V, y que “guarda” las distancias entre a y cada uno de los vértices de V.
Sea, finalmente, otro vector, P, con las mismas dimensiones que D, y que conserva la información sobre qué vértice precede a cada uno de los vértices en el camino.

El algoritmo para determinar el camino de longitud mínima entre los vértices a y z es:

C ← V
Para todo vértice i ∈ C, i ≠ a, se establece D_i ← ∞; D_a ← 0
Para todo vértice i ∈ C se establece P_i = a
Se obtiene el vértice s ∈ C tal que no existe otro vértice w ∈ C tal que D_w < D_s
- Si s = z entonces se ha terminado el algoritmo.
Se elimina de C el vértice s: C ← C−{s}
Para cada arista e ∈ A de longitud l, que une el vértice s con algún otro vértice t ∈ C,
- Si l+D_s < D_t, entonces:
  1. Se establece D_t ← l+D_s
  2. Se establece P_t ← s
Se regresa al paso 4

Al terminar este algoritmo, en D_z estará guardada la distancia mínima entre a y z. Por otro lado, mediante el vector P se puede obtener el camino mínimo: en P_z estará y, el vértice que precede a z en el camino mínimo; en P_y estará el que precede a y, y así sucesivamente, hasta llegar a a.

[editar] Complejidad

Orden de complejidad del algoritmo: O((V+E)(log V))

[editar] Pseudocódigo

Estructura de datos auxiliar: Q = Estructura de datos Cola de prioridad (se puede implementar con un heap)

   DIJKSTRA (Grafo G, nodo_fuente s)
       // inicializamos todos los nodos del grafo. La distancia de cada nodo es infinita
       // y los padres son NULL
       for u ∈ V[G] do
           distancia[u] = INFINITO
           padre[u] = NULL
       distancia[s] = 0
       //encolamos todos los nodos del grafo
       Encolar (cola, V[G])
       mientras cola != 0 do
          // OJO: Se extrae el nodo que tiene distancia mínima y se conserva la condición
          // de Cola de prioridad
           u = extraer_minimo(cola)
           for v ∈ adyacencia[u] do
               if distancia[v] > distancia[u] + peso(u,v) do
                   distancia[v] = distancia[u] + peso(u,v)
                   padre[v] = u

[editar] Otra version en pseudocodigo SIN COLA DE PRIORIDAD

funcion Dijkstra (Grafo G, nodo_salida s)
  //Usaremos un vector para guardar las distancias del nodo salida al resto
  //Inicializamos el vector con distancias iniciales
  boleano visto[n] // vector de boleanos para controlar los vertices de los que ya tenemos la distancia minima
  para cada w ∈ V[G] hacer
     Si (no existe arista entre s y w) entonces
         distancia[w] = Infinito //puedes marcar la casilla con un -1 por ejemplo
     Sino
         distancia[w] = peso (s,w)
     fsi 
  fpara
  distancia[s] = 0
  visto[s] = cierto
  //n es el numero de vertices que tiene el Grafo
  mientras (no_esten_vistos_todos) hacer 
     vertice = coger_el_minimo_del_vector distancia y que no este visto;
     visto[vertice] = cierto;
     para cada w ∈ sucesores(G,vertice) hacer
         si distancia[w]>distancia[vertice]+peso(vertice,w) entonces
            distancia[w] = distancia[x]+peso(vertice,w)
         fsi
     fpara
  fmientras
finfuncion

Al final tenemos en el vector distancia en cada posicion la distancia minima del vertice salida a otro vertice cualquiera.

[editar] Implementación

[editar] C++

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
 
#define FLSH gets(l)
 
int destino, origem, vertices = 0;
int custo, *custos = NULL;
 
void dijkstra(int vertices, int origen, int destino, int *costos) {
    int i, v, cont = 0;
    int *ant, *tmp;
    int *z;                 /* vertices para los cuales se conoce el camino minimo */
    double min;
    double *dist = new double[vertices];  /* vector con los costos de dos caminos */
 
    /* aloca las lineas de la matriz */
    ant = new int[vertices];
    tmp = new int[vertices];
    if (ant == NULL) {
        printf ("** Error: Memoria Insuficiente **");
        exit(-1);
    }
 
    z = new int[vertices];
    if (z == NULL) {
        printf ("** Error: Memoria Insuficiente **");
        exit(-1);
    }
 
    for (i = 0; i < vertices; i++) {
        if (custos[(origen - 1) * vertices + i] !=- 1) {
            ant[i] = origen - 1;
            dist[i] = costos[(origen-1)*vertices+i];
        }
        else {
            ant[i]= -1;
            dist[i] = HUGE_VAL;
        }
        z[i]=0;
    }
    z[origen-1] = 1;
    dist[origen-1] = 0;
 
    /* Bucle principal */
    do {
 
        /* Encontrando el vertice que debe entrar en z */
        min = HUGE_VAL;
        for (i=0;i<vertices;i++)
            if (!z[i])
                if (dist[i]>=0 && dist[i]<min) {
                    min=dist[i];v=i;
                }
 
        /* Calculando las distancias de los nodos vecinos de z */
        if (min != HUGE_VAL && v != destino - 1) {
            z[v] = 1;
            for (i = 0; i < vertices; i++)
                if (!z[i]) {
                    if (costos[v*vertices+i] != -1 && dist[v] + costos[v*vertices+i] < dist[i]) {
                        dist[i] = dist[v] + costos[v*vertices+i];
                        ant[i] =v;
                    }
                }
        }
 
    } while (v != destino - 1 && min != HUGE_VAL);
 
    /* Muestra el resultado de la búsqueda */
    printf("\tDe %d para %d: \t", origen, destino);
    if (min == HUGE_VAL) {
        printf("No Existe\n");
        printf("\tCosto: \t- \n");
    }
    else {
        i = destino;
        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--) {
            printf("%d -> ", tmp[i-1]);
        }
        printf("%d", destino);
 
        printf("\n\tCosto:  %d\n",(int) dist[destino-1]);
    }
}
 
void limpiar(void) {
    system("clear");//para limpiar pantalla
}
 
void menu(void) {
    limpiar();
    printf("Implementacion del Algoritmo de Dijasktra\n");
    printf("Comandos:\n");
    printf("\t d - Aniadir un Grafo\n"
           "\t r - Determinar el menor camino de los grafos\n"
           "\t CTRL+c - Sair del programa\n");
    printf(">>> ");
}
 
void add(void) {
    int i, j;
 
    do {
        printf("\nInforme o numero de vertices (no minimo 2 ): ");
        scanf("%d",&vertices);
    } while (vertices < 2 );
 
    if (!custos)
    free(custos);
    custos = (int *) malloc(sizeof(int)*vertices*vertices);
    for (i = 0; i <= vertices * vertices; i++)
        custos[i] = -1;
 
    printf("Entre las Aristas:\n");
 
    do {
 
        do {
            printf("Origen de arista (entre 1 y %d o '0' para salir): ", vertices);
            scanf("%d",&origem);
        } while (origem < 0 || origem > vertices);
 
        if (origem) {
            do {
                printf("Destino da arista (entre 1 e %d, menos %d): ", vertices, origem);
                scanf("%d", &destino);
            } while (destino < 1 || destino > vertices || destino == origem);
 
            do {
                printf("Costo (positivo) de arista a vertice %d para el vertice %d: ",
                origem, destino);
                scanf("%d",&custo);
            } while (custo < 0);
 
            custos[(origem-1) * vertices + destino - 1] = custo;
        }
 
    } while (origem);
}
 
void buscar(void) {
    int i, j;
 
    /* Azul */
    printf("{FONTE}33[36;1m");
    printf("Lista dos Menores Caminos en Grafo Dado: \n");
 
    for (i = 1; i <= vertices; i++) {
        for (j = 1; j <= vertices; j++)
            dijkstra(vertices, i,j, custos);
        printf("\n");
    }
 
    printf("<Presione ENTER para volver al menu principal>\n");
    /* Vuelve al color normal */
    printf("{FONTE}33[m");
}
 
int main(int argc, char **argv) {
    int i, j;
    char opcion[3], l[50];
 
    do {
 
        menu();
        scanf("%s", &opcion);
 
        if ((strcmp(opcion, "d")) == 0) {
            add();
        }
        FLSH;
 
        if ((strcmp(opcion, "r") == 0) && (vertices > 0) ) {
            buscar();
            FLSH;
        }
 
    } while (opcion!= "x");
 
    printf("\nHasta la proxima...\n\n");
 
    return 0;
}

[editar] Python

import sys
    infinity = sys.maxint - 1
 
    class Vertex(object):
        """Un vértice es un grafo, usando una lista de adyacencia.
 
        'edges' o 'arcos' es una secuencia o colección de tuplas (arcos), el primer elemento
        es el nombre de un vértice y el segundo elemento es la distancia a ese vértice.
        'name' o nombre es un identificador único para cada vértice, como el nombre de una
        ciudad, un entero, una tupla de coordenadas, etc. """
 
        def __init__(self, name, edges):
            self.name = name
            self.edges = edges
 
    def ShortestPath(graph, source, dest):
        """Devuelve la distancia más corta desde el vértice inicial a un destino, usando el
        algoritmo de Dijkstra.
        Asume que el grafo está conectado."""
 
        distances = {}
        names = {}
        for v in graph:
            distances[v.name] = infinity # Inicializa las distancias
            names[v.name] = v # Mapea los nombres a los vértices que representa
        distances[source.name] = 0 # La distancia desde el vértice inicial a sí mismo es 0
        dist_to_unknown = distances.copy() # Escoge el siguiente vértice a explorar
        last = source
        while last.name != dest.name:
            # Escoge el siguiente vértice a explorar, que no está todavía completamente explorado
            # y minimiza las distancias ya conocidas
            next = names[ min( [(v, k) for (k, v) in dist_to_unknown.iteritems()] )[1] ]
            for n, d in next.edges: # n es el nombre del vértice adyacente, d es la distancia a él
                distances[n] = min(distances[n], distances[next.name] + d)
                if n in dist_to_unknown:
                    dist_to_unknown[n] = distances[n]
            last = next
            if last.name in dist_to_unknown: # Borra el vértice explorado completamente
                del dist_to_unknown[next.name]

[editar] PHP

<?PHP
class Dijkstra {
 
        var $visited = array();
        var $distance = array();
        var $previousNode = array();
        var $startnode =null;
        var $map = array();
        var $infiniteDistance = 0;
        var $numberOfNodes = 0;
        var $bestPath = 0;
        var $matrixWidth = 0;
 
        function Dijkstra(&$ourMap, $infiniteDistance) {
                $this -> infiniteDistance = $infiniteDistance;
                $this -> map = &$ourMap;
                $this -> numberOfNodes = count($ourMap);
                $this -> bestPath = 0;
        }
 
        function findShortestPath($start,$to = null) {
                $this -> startnode = $start;
                for ($i=0;$i<$this -> numberOfNodes;$i++) {
                        if ($i == $this -> startnode) {
                                $this -> visited[$i] = true;
                                $this -> distance[$i] = 0;
                        } else {
                                $this -> visited[$i] = false;
                                $this -> distance[$i] = isset($this -> map[$this -> startnode][$i]) 
                                        ? $this -> map[$this -> startnode][$i] 
                                        : $this -> infiniteDistance;
                        }
                        $this -> previousNode[$i] = $this -> startnode;
                }
 
                $maxTries = $this -> numberOfNodes;
                $tries = 0;
                while (in_array(false,$this -> visited,true) && $tries <= $maxTries) {                  
                        $this -> bestPath = $this->findBestPath($this->distance,array_keys($this -> visited,false,true));
                        if($to !== null && $this -> bestPath === $to) {
                                break;
                        }
                        $this -> updateDistanceAndPrevious($this -> bestPath);                      
                        $this -> visited[$this -> bestPath] = true;
                        $tries++;
                }
        }
 
        function findBestPath($ourDistance, $ourNodesLeft) {
                $bestPath = $this -> infiniteDistance;
                $bestNode = 0;
                for ($i = 0,$m=count($ourNodesLeft); $i < $m; $i++) {
                        if($ourDistance[$ourNodesLeft[$i]] < $bestPath) {
                                $bestPath = $ourDistance[$ourNodesLeft[$i]];
                                $bestNode = $ourNodesLeft[$i];
                        }
                }
                return $bestNode;
        }
 
        function updateDistanceAndPrevious($obp) {            
                for ($i=0;$i<$this -> numberOfNodes;$i++) {
                        if(       (isset($this->map[$obp][$i])) 
                            &&  (!($this->map[$obp][$i] == $this->infiniteDistance) || ($this->map[$obp][$i] == 0 ))  
                                &&      (($this->distance[$obp] + $this->map[$obp][$i]) < $this -> distance[$i])
                        )  
                        {
                                        $this -> distance[$i] = $this -> distance[$obp] + $this -> map[$obp][$i];
                                        $this -> previousNode[$i] = $obp;
                        }
                }
        }
 
        function printMap(&$map) {
                $placeholder = ' %' . strlen($this -> infiniteDistance) .'d';
                $foo = '';
                for($i=0,$im=count($map);$i<$im;$i++) {
                        for ($k=0,$m=$im;$k<$m;$k++) {
                                $foo.= sprintf($placeholder, isset($map[$i][$k]) ? $map[$i][$k] : $this -> infiniteDistance);
                        }
                        $foo.= "\n";
                }
                return $foo;
        }
 
        function getResults($to = null) {
                $ourShortestPath = array();
                $foo = '';
                for ($i = 0; $i < $this -> numberOfNodes; $i++) {
                        if($to !== null && $to !== $i) {
                                continue;
                        }
                        $ourShortestPath[$i] = array();
                        $endNode = null;
                        $currNode = $i;
                        $ourShortestPath[$i][] = $i;
                        while ($endNode === null || $endNode != $this -> startnode) {
                                $ourShortestPath[$i][] = $this -> previousNode[$currNode];
                                $endNode = $this -> previousNode[$currNode];
                                $currNode = $this -> previousNode[$currNode];
                        }
                        $ourShortestPath[$i] = array_reverse($ourShortestPath[$i]);
                        if ($to === null || $to === $i) {
                        if($this -> distance[$i] >= $this -> infiniteDistance) {
                                $foo .= sprintf("no route from %d to %d. \n",$this -> startnode,$i);
                        } else {
                                $foo .= sprintf('%d => %d = %d [%d]: (%s).'."\n" ,
                                                $this -> startnode,$i,$this -> distance[$i],
                                                count($ourShortestPath[$i]),
                                                implode('-',$ourShortestPath[$i]));
                        }
                        $foo .= str_repeat('-',20) . "\n";
                                if ($to === $i) {
                                        break;
                                }
                        }
                }
                return $foo;
        }
} // end class 
?>

[editar] Enlaces externos

Wikimedia Commons alberga contenido multimedia sobre Algoritmo de Dijkstra.Commons
Analiza Algoritmo de Dijkstra en JavaScript
Applets en Java para probar el algoritmo de Dijkstra (Inglés)
Graph módulo Perl en CPAN
Arquimedex.com Tutorial del Algoritmo de Dijkstra
Video Tutorial del Algoritmo de Dijkstra
giswiki.net Algoritmo de Dijkstra en lenguajes como PHP, Actionscript y otros

Categorías: Algoritmos de búsqueda | Teoría de grafos | Módulos Perl

See also ebooksgratis.com: no banners, no cookies, totally FREE.