ALGORITMO DE DIJKSTRA PRIM KRUSKAL FLOYD WARSHALL

ALGORITMO DE DIJKSTRA
Definición
También llamado algoritmo de caminos mínimos, es un algoritmo que permite encontrar del camino más corto desde un vértice origen, a los demás vértices de un grafo dirigido o al vértice destino de dicho grafo dirigido y con determinados pesos o capacidades en cada una de sus aristas. En la mayoría de aplicaciones donde se emplean los grafos, es necesario conocerel camino de menor costo entre dos vértices dados. Como por ejemplo:
Distribución de productos a una red de establecimientos comerciales.
Distribución de correos postales.
Sea G = (V, A) un grafo dirigido ponderado.
Así, mismo, el problema del camino más corto de un vértice a otro consiste en determinar el camino de menor costo, desde un vértice u a otro vértice v, y el costo de un camino es lasuma de los costos (pesos) de los arcos que lo conforman.
Objetivo
Como bien lo dice su definición, el objetivo de 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 vértice destino o al resto de vértices que componen el grafo, el algoritmo sedetiene. Este algoritmo es una especialización de la búsqueda de costo uniforme, por tanto no funciona en grafos con aristas de costo con valor negativo. 
Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector V de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.
1. Inicializar todas las distancias en V con un valorinfinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
2. Sea a = x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi.
4. Si la distancia desde x hasta vi guardada en V es mayor que la distancia desde x hasta a sumada a la distancia desde ahasta vi; esta se sustituye con la segunda nombrada, esto es:
si (Vi > Va + d(a, vi)) entonces Vi = Va + d(a, vi)
5. Marcamos como completo el nodo a.
6. Tomamos como próximo nodo actual el de menor valor en V (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.
Una vez terminado al algoritmo, V estará completamente lleno.Estructura
El pseudocódigo del Algoritmo de Dijkstra es el siguiente:























Pasos del algoritmo
Sea V un conjunto de vértices de un grafo.
Sea C una matriz de costos de las aristas del grafo, donde en C [u,v] se almacena el costo de la arista entre u y v.
Sea S un conjunto que contendrá los vértices para los cuales ya se tiene determinado el camino mínimo.
Sea D un arreglounidimensional tal que D[v] es el costo del camino mínimo del vértice origen al vértice v.
Sea P un arreglo unidimensional tal que P[v] es el vértice predecesor de v en el camino mínimo que se tiene construido.
Sea v inicial el vértice origen.
Paso 1. S ← {vinicial} //Inicialmente S contendrá el vértice //origen

Paso 2. Para cada v∈V, v ≠ vinicial, hacer

2.1. D[v] ← C [vinicial, v] //Inicialmente elcosto del //camino mínimo de vinicial a v es lo contenido en //la matriz de costos
2.2. P[v] ← vinicial //Inicialmente, el //predecesor de v en el camino mínimo construido //hasta el momento es vinicial

Paso 3. Mientras (V – S ≠ ∅) hacer //Mientras existan vértices para //los cuales no se ha determinado el //camino mínimo
3.1. Elegir un vértice w∈ (V-S) tal que D[w] sea el mínimo.3.2. S ← S ∪ {w} //Se agrega w al conjunto S, pues ya se //tiene el camino mínimo hacia w
3.3. Para cada v∈ (V-S) hacer
3.3.1. D[v] ← min (D[v], D[w]+C [w,v]) //Se escoge, entre //el camino mínimo hacia v que se tiene //hasta el momento, y el camino hacia v //pasando por w mediante su camino mínimo, //el de menor costo.
3.3.2. Si min (D[v], D[w]+C [w,v]) = D[w]+C[w,v] entonces P[v] ←...