algoritmo de floyd

• Dado un grafo dirigido con pesos, ¿cuales son las trayectorias de largos caminos ( es decir "distancias mas cortas") entre todos los pares de vertices?
• La matriz de distancias (matriz de pesos) sirve como punto de partida. Se realizan K iteraciones sobre la matriz buscando el camino mas corto.
• FLOYD calcula los caminos mas cortos entre todos los vertices de un grafo.

• Se basa en el siguiente principio
• Tomamos un vertice A
• Calculamos que sale mas varato, si 
• movernos entre B y C directamente o
• movernos entre B y C pasando por A

ALGORITMO:

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: