Esta es una representación gráfica de un grafo:

Los nodos se representan como círculos de colores y

los arcos se representan como líneas que conectan los
círculos.
💡 Dato: dos nodos están conectados si existe un arco
entre ellos.
Aplicaciones
Los grafos se pueden aplicar directamente a escenarios de
la vida real. Por ejemplo, podríamos usar grafos para
modelar una red de transporte, en la cual los nodos
representarían instalaciones para enviar o recibir
productos y los arcos representarían caminos que los
conectan (como en el siguiente diagrama).

Red representada como un grafo.

Tipos de grafos
Los grafos pueden ser:
 No dirigido: si para cada par de nodos conectados,
puedes ir de un nodo al otro en ambas direcciones.

 Dirigido: si para cada par de nodos conectados, solo

puedes ir de un nodo a otro en una dirección específica.
Usamos flechas en lugar de líneas sencillas para
representar arcos dirigidos.

💡 Dato: en este artículo, trabajaremos con grafos no

dirigidos.
Grafo ponderado
Un grafo ponderado es un grafo cuyos arcos tienen un
"peso", "valor", o "costo" asociado. El valor de cada arco
puede representar la distancia, tiempo, u otro valor que
modele la conexión entre el par de nodos que conecta.
Por ejemplo, en el grafo ponderado que tenemos a
continuación, puedes ver un número azul junto a cada
arco. Este número representa el valor o costo del arco
correspondiente.
🔸Introducción al algoritmo de
Dijkstra
comencemos a ver más detalles sobre este algoritmo.

Propósito y Usos
Con el algoritmo de Dijkstra, puedes encontrar la ruta más
corta o el camino más corto entre los nodos de un grafo.
Específicamente, puedes encontrar el camino más corto
desde un nodo (llamado el nodo de origen) a todos los
otros nodos del grafo, generando un árbol del camino más
corto.
Este algoritmo es usado por los dispositivos GPS para
encontrar el camino más corto entre la ubicación actual y
el destino del usuario. Tiene amplias aplicaciones en la
industria, especialmente en aquellas áreas que requieren
modelar redes.

Historia
Fue creado y publicado por el Dr. Edsger W. Dijkstra, un
científico Neerlandés brillante en ciencias de la
computación e ingeniería de software.
En 1959, publicó un artículo de tres páginas titulado: "A
note on two problems in connexion with graphs", lo cual se
traduce a español como "Una nota sobre dos problemas
relacionados con grafos." En este artículo explicó su nuevo
algoritmo.
Dr. Edsger Dijkstra en ETH Zurich en 1994 (imagen de Andreas F. Borchert)
Durante una entrevista en 2001, el Dr. Dijkstra reveló
cómo y por qué diseñó el algoritmo:

¿Cuál es el camino más corto para viajar desde Rotterdam

a Groningen? Es el algoritmo para el camino más corto, el
cual diseñé en aproximadamente 20 minutos. Una mañana
estaba comprando en Amsterdam con mi joven prometida,
y cansados, nos sentamos en una terraza de un café para
beber una taza de café y estaba pensando cómo podría
hacerlo, y luego diseñé el algoritmo para el camino más
corto. Como acabo de mencionar, fue un invento de 20
minutos. De hecho, fue publicado en 1959, tres años más
tarde. La publicación sigue siendo bastante buena. Una de
las razones de por qué es tan buena es que la diseñé casi
sin lápiz ni papel. Sin lápiz ni papel no tienes otra opción
más que evitar todas las complejidades que se puedes
evitar. Con el tiempo, ese algoritmo se convirtió, para mi
sorpresa, en una de las piedras angulares de mi fama. -
Cita de Edsger W. Dijkstra en el artículo An interview with
Edsger W. Dijkstra.

Texto original en inglés:

What’s the shortest way to travel from Rotterdam to

Groningen? It is the algorithm for the shortest path, which I
designed in about 20 minutes. One morning I was shopping
in Amsterdam with my young fiancée, and tired, we sat
 down on the café terrace to drink a cup of coffee and I was
just thinking about whether I could do this, and I then
designed the algorithm for the shortest path. As I said, it
was a 20-minute invention. In fact, it was published in
1959, three years later. The publication is still quite nice.
One of the reasons that it is so nice was that I designed it
without pencil and paper. Without pencil and paper you are
almost forced to avoid all avoidable complexities.
Eventually that algorithm became, to my great
amazement, one of the cornerstones of my fame. — As
quoted in the article Edsger W. Dijkstra from An interview
with Edsger W. Dijkstra.
⭐ Increíble, ¿cierto? En tan solo 20 minutos, el Dr.
Dijkstra diseñó uno de los algoritmos más famosos de la
historia de la ciencia de la computación.
Aspectos básicos del algoritmo de
Dijkstra
 El algoritmo de Dijkstra básicamente inicia en el nodo
que selecciones (el nodo de origen) y analiza el grafo para
encontrar el camino más corto entre ese nodo y todos los
otros nodos en el grafo.
 El algoritmo mantiene un registro de la distancia
conocida más corta desde el nodo de origen hasta cada
nodo y actualiza el valor si encuentra un camino más corto.
 Una vez que el algoritmo ha encontrado el camino más
corto entre el nodo de origen y otro nodo, ese nodo se
marca como "visitado" y se agrega al camino.
 El proceso continúa hasta que todos los nodos en el
grafo han sido añadidos al camino. De esta forma, tenemos
un camino que conecta al nodo de origen con todos los
otros nodos siguiendo el camino más corto posible para
llegar a cada uno de ellos.
Requisitos
El algoritmo de Dijkstra solo puede aplicarse a grafos con
arcos cuyos valores o pesos son positivos. Esto se debe a
que durante es proceso, los valores de los arcos deben ser
sumados para encontrar el camino más corto.
Si existe un valor negativo en el grafo, el algoritmo no
funcionará correctamente. Una vez que el nodo se marca
como "visitado", el camino actual hacia ese nodo se marca
como el camino más corto para alcanzar ese nodo pero los
valores negativos pueden cambiar esto si el valor total
puede ser reducido luego de este paso.

🔹Ejemplo del algoritmo de

Dijkstra
cómo funciona un ejemplo paso a paso.

Tenemos el siguiente grafo:

El algoritmo generará el camino más corto desde el

nodo 0 hasta todos los demás nodos del grafo.
Obtendremos el camino más corto desde el nodo 0 hasta el
nodo 1, desde el nodo 0 hasta el nodo 2, desde el
nodo 0 hasta el nodo 3 y así sucesivamente para cada nodo
del grafo.
Inicialmente, tendremos esta lista de distancias (en la
siguiente imagen):
También tendremos esta lista para mantener un registro
de los nodos que todavía no se han visitado (los que no
han sido incluidos en el camino). Los llamaremos "nodos
por visitar":

💡 Dato: Recuerda que el algoritmo se completa cuando

todos los nodos han sido agregados al camino final que
conecta al nodo de origen con todos los otros nodos a
través del camino más corto.
Como escogemos iniciar en el nodo 0, podemos marcar
este nodo como visitado. Lo tachamos de la lista de nodos
por visitar y añadimos un borde rojo al nodo
correspondiente en el diagrama:
Ahora debemos comenzar a verificar la distancia desde el
nodo 0 hasta sus nodos adyacentes. Como puedes ver,
estos nodos son el nodo 1 y el nodo 2 (conectados por los
arcos rojos en el diagrama):

💡 Dato: esto no significa que estamos añadiendo los nodos

adyacentes inmediatamente al camino más corto. Antes de
añadir un nodo a este camino, debemos verificar si ya
encontramos el camino más corto para alcanzarlo. Solo
estamos haciendo un proceso de verificación inicial para
ver las opciones disponibles.
Debemos actualizar las distancias desde el nodo 0 hasta el
nodo 1 y el nodo 2 con los valores de los arcos que los
conectan con el nodo 0 (el nodo de origen).
Estos valores son, respectivamente:

Después de actualizar las distancias a los nodos

adyacentes, debemos:
 Seleccionar el nodo más cercando al nodo de origen
en base a las distancias que conocemos hasta el momento.
 Marcarlo como visitado.
 Añadirlo al camino.
Si verificamos la lista de distancias, podemos ver que el
nodo 1 tiene la menor distancia hasta el nodo de origen
(una distancia de 2), así que lo añadimos al camino.
En el diagrama, podemos representar esto con un borde
rojo:

Lo marcamos con un cuadrado rojo en la lista para

representar que ha sido "visitado" y que ya hemos
encontrado el camino más corto hasta este nodo:

Lo tachamos de la lista de nodos pendientes por visitar:

Ahora tenemos que analizar los nuevos nodos adyacentes
para encontrar el camino más corto para llegar a ellos.
Solo analizaremos los nodos que son adyacentes a los
nodos que ya son parte del camino más corto (el camino
marcado con arcos rojos).

Los nodos 3 y 2 son adyacentes a los nodos que ya están

en el camino porque están directamente conectados al
nodo 1 y al nodo 0, respectivamente (como puedes ver en
el siguiente diagrama). Estos son los nodos que
analizaremos en el próximo paso.

Como ya tenemos la distancia desde el nodo de origen al

nodo 2 escrita en nuestra lista, no tenemos que actualizar
la distancia esta vez. Solo debemos actualizar la distancia
desde el nodo de origen hasta el nuevo nodo adyacente (el
nodo 3).
 Esta distancia es 7. Veamos por qué.
Para encontrar la distancia desde el nodo de origen hasta
otro nodo (en este caso, el nodo 3), sumamos los valores
de todos los arcos que forman el camino más corto para
alcanzar ese nodo:
 Para el nodo 3: la distancia total es 7 porque
sumamos los valores de los arcos que forman el camino 0 -
> 1 -> 3 (2 para el arco 0 -> 1 y 5 para el arco 1 -> 3).

Ahora que ya tenemos la distancia hasta los nodos

adyacentes, debemos escoger el nodo que será añadido al
camino más corto. Debemos seleccionar el
nodo pendiente por visitar con la distancia más corta
(conocida hasta el momento) hasta el nodo de origen.
A partir de la lista de distancias, podemos detectar
inmediatamente que este nodo es el nodo 2, con una
distancia de 6:

Lo agregamos al camino de forma gráfica con un borde

rojo alrededor del nodo y un arco rojo:

También lo marcamos como visitado agregando un

cuadrado rojo pequeño en la lista de distancias y lo
tachamos de la lista de nodos pendientes por visitar.
Ahora tenemos que repetir el proceso para encontrar el
camino más corto desde el nodo de origen hasta el nuevo
nodo adyacente, el cual es el nodo 3.
Puedes ver que tenemos dos caminos posibles: 0 -> 1 ->
3 o 0 -> 2 -> 3. Veamos cómo podemos determinar cuál es
el camino más corto.

El nodo 3 ya tiene una distancia en la lista que registramos

previamente (7 en la lista que vemos en la siguiente
imagen). Esta distancia fue el resultado de un paso previo
en el cual sumamos los valores 5 y 2 de los dos arcos que
necesitamos recorrer para seguir el camino 0 -> 1 -> 3.
Pero ahora tenemos otra alternativa. Si escogemos seguir
el camino 0 -> 2 -> 3, necesitaríamos recorrer dos arcos 0 -
> 2 y 2 -> 3 con valores 6 y 8, respectivamente, los cual
representa una distancia total de 14.

La primera distancia es más corta (7 vs. 14), así que

escogeremos mantener el camino original 0 -> 1 -> 3. Solo
actualizamos la distancia si el camino nuevo es más
corto.
Por lo tanto, añadimos este nodo al camino con la primera
opción: 0 -> 1 -> 3.

Marcamos este nodo como visitado y lo tachamos de la

lista de nodos pendientes por visitar:
 Ahora repitamos el proceso nuevamente.

Debemos verificar los nuevos nodos adyacentes que no

hemos visitado hasta el momento. Esta vez, estos nodos
son el nodo 4 y el nodo 5 ya que son adyacentes al nodo 3.

Actualizamos las distancias entre estos nodos y el nodo de

origen, siempre intentando encontrar el camino más corto,
si es posible:

 Para el nodo 4: la distancia es 17 en el camino 0 -> 1

-> 3 -> 4.
 Para el nodo 5: la distancia es 22 en el camino 0 -> 1
-> 3 -> 5.
💡 Dato: nota que solo podemos considerar extender el
camino más corto (marcado en rojo). No podemos
considerar caminos que nos llevan a través de arcos que
no han sido añadidos al camino más corto (por ejemplo, no
podemos usar un camino que atraviese el arco 2 -> 3).

Debemos escoger el nodo pendiente por visitar que ahora

será marcado como visitado. En este caso, este el
nodo 4 porque tiene la distancia más corta de la lista de
distancias.
Lo agregamos de forma gráfica al diagrama:

También lo marcamos como "visitado" agregando un

cuadrado rojo pequeño en la lista:
 Y lo tachamos de la lista de nodos pendientes por visitar:

Repetimos el proceso nuevamente.

Verificamos los nodos adyacentes: el nodo 5 y el nodo 6.

Debemos analizar cada camino posible que podemos
seguir para alcanzarlos a partir de nodos que ya han sido
marcados como visitados y que ya han sido agregados al
camino.

Para el nodo 5:
 La primera opción es seguir el camino 0 -> 1 -> 3 -> 5,
el cual tiene una distancia de 22 desde el nodo de origen
 (2 + 5 + 15). Esta distancia ya se registró en la lista de
distancias en un paso previo.
 La segunda opción sería seguir el camino 0 -> 1 -> 3 ->
4 -> 5, el cual tiene una distancia de 23 a partir del nodo
de origen (2 + 5 + 10 + 6).
El primer camino es más corto, así que lo escogemos para
el nodo 5.
Para el nodo 6:
 El camino que podemos seguir es 0 -> 1 -> 3 -> 4 -> 6,
el cual tiene una distancia de 19 a partir del nodo de
origen (2 + 5 + 10 + 2).

Marcamos el nodo con la menor distancia que conocemos

hasta el momento como "visitado." En este caso, el nodo 6.

Y lo tachamos de la lista de nodos pendientes por visitar:

Ahora tenemos este camino (marcado en rojo):

 Solo nos falta un nodo que no ha sido visitado, el nodo 5.
Veamos cómo podemos incluirlo en el camino.
Existen tres posibles caminos que podemos escoger para
alcanzar el nodo 5 a partir de los nodos que hemos añadido
al camino:
 Opción 1: 0 -> 1 -> 3 -> 5 con una distancia de 22 (2
+ 5 + 15).
 Opción 2: 0 -> 1 -> 3 -> 4 -> 5 con una distancia
de 23 (2 + 5 + 10 + 6).
 Opción 3: 0 -> 1 -> 3 -> 4 -> 6 -> 5 con una distancia
de 25 (2 + 5 + 10 + 2 + 6).

Seleccionamos el camino más corto: 0 -> 1 -> 3 -> 5 con

una distancia de 22.
Marcamos el nodo como "visitado" y lo tachamos de la lista
de nodos pendientes por visitar:

Y voilà! Tenemos el resultado final con el camino más

corto desde el nodo 0 hasta cada nodo del grafo.
 En el diagrama, las líneas rojas indican los arcos que
pertenecen al camino más corto. Debes seguir estos
arcos para seguir el camino más corto para alcanzar un
nodo en el grafo, si inicias el recorrido desde el nodo 0.
Por ejemplo, si quieres llegar al nodo 6 iniciando desde el
nodo 0, solo necesitas seguir los arcos rojos y estarás
siguiendo el camino más corto automáticamente (0 -> 1 ->
3 -> 4 - > 6).

🔸 En resumen
 Los grafos son usados para modelar conexiones entre
objetos, personas o entidades. Tienen dos elementos
principales: nodos y arcos. Los nodos representan objetos
y los arcos representan las conexiones entre esos objetos.
 El algoritmo de Dijkstra encuentra el camino más corto
entre un nodo dado (el nodo de origen) y todos los otros
nodos del grafo.
 Este algoritmo usa los valores de los arcos para
encontrar el camino que minimiza el valor total entre el
nodo de origen y los demás nodos del grafo. Este valor
depende de lo que representa el valor de los arcos en el
grafo. Puede ser, por ejemplo, tiempo, costo o distancia.