Encuentre el camino más corto entre dos puntos en un gráfico con el algoritmo de Dijkstra

Encontrar la ruta más corta entre dos puntos en un gráfico es un problema común en las estructuras de datos, especialmente cuando se trata de optimización.

Un gráfico es una serie de nodos conectados por bordes. Los gráficos pueden ser ponderados (los bordes tienen valores) y direccionales (los bordes tienen dirección).

Algunas aplicaciones de esto son la optimización de la trayectoria de vuelo o 6 grados de Kevin Bacon.

Algoritmo de Dijkstra

La solución más común para este problema es el algoritmo de Dijkstra que actualiza la ruta más corta entre el nodo actual y todos sus vecinos.

Después de actualizar la distancia de todos los vecinos, se mueve al nodo con la distancia más baja y repite el proceso con todos los vecinos no visitados. Este proceso continúa hasta que se haya visitado todo el gráfico.

Imagen de niveles de código

Paso 0:

Nuestro gráfico debe configurarse para que podamos registrar los valores requeridos. En cualquier borde tenemos la distancia entre los dos nodos que conecta. En cualquier nodo tenemos su distancia más corta desde el nodo inicial.

Establezcamos el valor en cada nodo en infinito positivo y establezcamos el valor en el nodo inicial en cero.

Paso 1:

Mire todos los nodos directamente adyacentes al nodo inicial. Los valores que llevan los bordes que conectan el inicio y estos nodos adyacentes son las distancias más cortas a cada nodo respectivo.

Registre estas distancias en el nodo, sobrescribiendo el infinito, y también tache los nodos, lo que significa que se ha encontrado su camino más corto.

Paso 2:

Seleccione uno de los nodos que haya calculado su ruta más corta, lo llamaremos nuestro pivote. Mire los nodos adyacentes a él (los llamaremos nuestros nodos de destino) y las distancias que los separan.

Para cada nodo de destino:

  • Si el valor en el pivote más el valor del borde que lo conecta totaliza menos que el valor del nodo de destino, actualice su valor, ya que se encontró una nueva ruta más corta.
  • Si se han explorado todas las rutas a este nodo de destino, se puede tachar.

Paso 3:

Repita el paso 2 hasta que se hayan tachado todos los nodos. Ahora tenemos un gráfico donde los valores retenidos en cualquier nodo serán la distancia más corta desde el nodo de inicio.

Más información:

Más sobre el algoritmo de Dijkstra

Otros algoritmos de ruta más corta