¿Qué es el algoritmo de Dijkstra?

Es un algoritmo que se aplica sobre un grado para encontrar el camino de coste mínimo entre un nodo de origen y un nodo de destino.

Procedimiento

1. Partimos de un vértice inicial y vamos a calcular el camino más corto a los restantes vértices del grafo accesibles desde él.
2. Junto a cada uno de los vértices restantes, anotaremos cuál es su distancia mínima provisional al inicial cuál es el vértice anterior en el camino más corto del inicial a él mismo.

Ejemplo aplicando Dijkstra

En el siguiente ejemplo vamos a buscar el más corto para llegar desde el nodo A hacia el nodo B

0**- Primer paso**

Hacemos una tabla con los valores iniciales, llegar desde A hacia el mismo lugar cuesta 0 y hasta los demás infinito (notación que se suele usar) porque no

1- Agregamos el camino hacia dos nodos

Ahora se agrego el camino hacia los dos nodos adyacentes de A, además agregamos el costo que toma llegar a cada uno y desde que nodo llegamos (venimos del A).

2- Avanzamos un paso más

Apoyándonos en el nodo C, vemos sip odemos llegar hacia B con un coste menor y también cuanto cuesta llegar a D. Esta vez dejamos asentado que el último nodo por el que pasamos fue C.

Como encontramos una manera menos costosa de llegar a B (Yendo primero a C y luego hacia B) entonces dejamos establecida esta nueva que encontramos.

3- Avanzamos un paso más

Comparamos por cuál camino es menos costoso llegar hacia D, donde las posibles opciones son 11 desde C y 7 desde B, nos quedamos con el camino de llegad es de B porque es el menos costoso(mirar la ultima columna).