10# Algoritmo de Dijkstra

En este episodio hablaré un poco sobre uno de los algoritmosque existen para determinar cuáles serían las mejores rutas en un grafo con métodos distintos.

Dijkstra

Este es un algoritmo eficiente (de complejidad O (n**2)), 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 Edsger Wybe Dijkstra en 1959.

Este algoritmo es un típico ejemplo de algoritmo ávido, que resuelven los problemas en sucesivos pasos, seleccionando en cada paso la solución más óptima con el objeto de resolver el problema

“Dado un grafo a cuyos arcos se han asociado una seria 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”.

Aquí les presento el algoritmo:

1-       Seleccionar el vértice de partida, un origen.

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

3-      Determinar los caminos especiales desde el nodo de partida.

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

5-      Para cada vértice 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 vértice.

6-      Para seleccionar un nuevo vértice no marcado como referencia, deberá tomarse aquel cuyo camino especial para llegar a él es el mínimo, por ejemplo, si anteriormente marqué el vértice 2, el cual tiene dos vértices adyacentes 3 y 4 cuyo peso en la arista corresponde a 10 y 5 respectivamente, se tomará como nuevo vértice de partida el 4, ya que el peso de la arista 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 el resto de nodos, pasando únicamente por caminos especiales, es decir vértices marcados.