algoritmos de grafos

Algoritmo de Dijkstra

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 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).
TEOREMA: El Algoritmo de Dijkstra realiza O(n²) operaciones (sumas y comparaciones) para determinar la longitud del camino más corto entre dos vértices de un grafo ponderado simple, conexo y no dirigido con n vértices.

Pseudocódigo

función Dijkstra (Grafo G, nodo_salida s)

  //Usaremos un vector para guardar las distancias del nodo salida al resto

  entero distancia[n] //Inicializamos el vector con distancias iniciales

  booleano visto[n] //vector de boleanos para controlar los vertices de los que ya tenemos la distancia mínima

  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

     Si_no

         distancia[w] = peso (s, w)

     fin si

  fin para

  distancia[s] = 0

  visto[s] = cierto

  //n es el número de vertices que tiene el Grafo

  mientras que (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[vertice]+peso (vertice, w)

         fin si

     fin para

  fin mientras

fin función

http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra