Metodo de Djistra(La ruta mas corta)

 El algoritmo de Dijkstra es un algoritmo eficiente (de complejidad O (n2 ), donde “n” es el número de vértices) que sirve para encontrar el camino de coste mínimo desde un nodo origen a todos los demás nodos del grafo. Fue diseñado por el holandés Edge Weber Dijkstra en 1959. Este algoritmo es un típico ejemplo de algoritmo ávido, que resuelve los problemas en sucesivos pasos, seleccionando en cada paso la solución más óptima con el objeto de resolver el problema. El fundamento sobre el que se basa este algoritmo es el principio de optimizar: si el camino más corto entre los vértices “u” y “v” pasa por el vértice “w”, entonces la parte del camino que va de “w” a “v” debe ser el camino más corto entre todos los caminos que van de “w” a “v”. De esta manera, se van construyendo sucesivamente los caminos de coste mínimo desde un vértice inicial hasta cada uno de los vértices del grafo, y se utilizan los caminos conseguidos como parte de los nuevos caminos. Dicho en otras palabras: “Dado un grafo a cuyos arcos se han asociado una serie de pesos, se define el camino de coste mínimo de un vértice “u” a otro “v”, como el camino donde la suma de los pesos de los arcos que lo forman es la más baja entre las de todos los caminos posibles de “u” a “v”.”

A continuación se presenta el algoritmo. Para la explicación general se tomará como referencia los siguientes pasos: 

1. Seleccionar vértice de partida, es decir un origen.

 2. Marcar el punto de partida como el punto de inicio. 

3. Determinar los caminos especiales desde el nodo de partida, es decir, el de inicio. 

4. Camino especial es aquel que solo puede trazarse a través de los nodos o vértices ya marcados.

 5. Para cada nodo no marcado, se debe determinar si es mejor usar el camino especial antes calculado o si es mejor usar el nuevo camino especial que resulte al marcar este nuevo nodo.

 6. Para seleccionar un nuevo nodo no marcado como referencia, deberá tomarse aquel cuyo camino especial para llegar a él es el mínimo, por ejemplo si anteriormente marqué el nodo o vértice 2, el cual tiene dos nodos adyacentes 3 y 4 cuyo peso en la arista  corresponde a 10 y 5 respectivamente, se tomará como nuevo nodo de partida el 4, ya que el peso de la arista o camino es menor.

 7. Cada camino mínimo corresponde a la suma de los pesos de las aristas que forman el camino para ir del nodo principal al resto de nodos, pasando únicamente por caminos especiales, es decir nodos marcados.