algoritmo de dijkstra

• Frecuentemente se desea conocer en una red cual es el camino mas corto entre un par de vértices, donde la longitud de un camino es la suma de las aristas.
• En este caso:
• si importa cuantos caminos existen
• si ya conozco un camino, pero encuentro otro uno mejor, sustituir
• se aplica el algoritmo de DIJKSTRA
• es un algoritmo eficiente ya que resuelve el problema en sucesivos pasos
• en cada paso se selecciona la solucion mas optima
• dado un V, DIJSKTRA busca un conjunto D con las menores distancias de V al resto de vertices
• al inicio solo conocemos:
• las distancias de los adyacentes
• D es inicializada a factor de peso (con el peso) para los adyacentes, Infinito (un numero muy grande como MAX-INT por ejemplo) para los no adyacentes 
• D va ser mejorado sucesivamente
• escogiendo el vértice V_{k no elegidos antes que tenga la distancia mas corta V0 ,}V_k
• probamos si pasando por Vk se puede obtener distancias mas cortas de las que tenemos para cada vértice restante del grafo.

PSEUDOCODIGO:

• Se considera al vertice 1 como el vertice origen. N es el numero de vertices de la grafica dirigida. S y D son arreglos de N elementos y M es una matriz de NxN elementos.
• V: todos los vertices
• S: vertices vicitados
• (V - S): vertices no visitados
• D[ W ]: vertice intermedio (actual)
•  D[ V ]: distancia vertice evaluado
• M[ V, W ]: valor de la matriz en el vertice intermedio

1. agregar el vertice 1 a S
2. repetir con i desde 2 hasta N
1. elegir un vertice V en (V - S) tal que D[ V ] sea el minimo valor
2. agregar V a S
3. repetir para cada vertice W en (V - S)
1. hacer D[ W ] = minimo ( D[ W ], D[ V ] + M[ V, W ])
4. fin de ciclo
3. fin de ciclo. 

IMPLEMENTACION EN C

La codificación que se realiza considera que el grafo esta representado con una matriz de pesos o costes. Esta contiene el coste de cada arco; si no hay arco entre dos vértices, la posición de la matriz contiene INFINITO (constante con un valor inalcanzable). Como cada vértice tiene asociado dos informaciones, ultimo vértice en el camino mínimo y la distancia mínima, se define una estructura que los agrupa y una tabla de tantas posiciones como vértices. El conjunto F de vértices se representa de la forma mas sencilla, un array de ceros y unos, de tal forma que si el vértice i se incluye en F, entonces F [ i ] se pone a 1. En esta codificación, se supone que el numero de vértices es n, o pudiendo superar la constante N. Ademas, el vértice origen es el de indice 0. 

(Algoritmos y Estructuras de Datos Una Perspectiva En C)