El algoritmo de Dijkstra en Python & C++ (Ejemplo)

¿Qué es el camino más corto o la distancia más corta?

El camino desde el vértice de origen hasta el vértice de destino que requiere el mínimo coste es el camino más corto o la distancia más corta. En teoría de grafos, es posible tener múltiples rutas desde un origen hasta un destino. Entre estas rutas, si existe una que requiere el mínimo coste, la denominamos camino más corto.

Aquí, “costo” se refiere al número de nodos en la ruta o a la suma de los costos en cada arista. Un camino puede tener una o varias aristas. La conexión entre dos vértices se denomina “arista”. Existen diversos algoritmos para encontrar el camino más corto, como el algoritmo de Dijkstra y el algoritmo de Bellman-Ford.

Aquí hablaremos del algoritmo de Dijkstra. Veamos el siguiente grafo ponderado:

Un gráfico ponderado no dirigido

• El término “ponderado” se refiere al costo de moverse de un nodo a otro. Por ejemplo, al moverse del nodo 1 al nodo 2, el costo o ponderación es 1.
• El camino entre el nodo 1 y el nodo 2 se denomina arista.
• “No dirigido” significa que puedes moverte de un nodo a otro y volver al nodo anterior. Por lo tanto, si intentamos encontrar todas las rutas del nodo 1 al nodo 7, serán:

Entre estas cuatro rutas, podemos ver que la primera ruta cuesta 7. Por lo tanto, es el camino más corto en términos de costo.

Ruta más corta

Cómo funciona el algoritmo de Dijkstra

El algoritmo de Dijkstra puede encontrar la distancia más corta en grafos ponderados, tanto dirigidos como no dirigidos. Este algoritmo es voraz porque siempre elige el nodo más corto o más cercano al origen. El término "voraz" significa que, entre un conjunto de resultados posibles, el algoritmo seleccionará el mejor.

Aquí, estamos tratando de encontrar los caminos más cortos entre todas las demás rutas. Entonces, el algoritmo de Dijkstra encuentra todos los caminos más cortos desde un único nodo de origen. Como resultado, se comporta como un algoritmo codicioso.

En la sección de “ejemplos” que aparece a continuación, verá el procedimiento paso a paso. Funciona de la siguiente manera:

Paso 1) Inicializa el nodo inicial con un coste de 0 y el resto de los nodos con un coste infinito.
Paso 2) Mantenga una matriz o lista para guardar track de los nodos visitados.
Paso 3) Actualiza el costo del nodo con el costo mínimo. Esto se puede hacer comparando el costo actual con el costo de la ruta (como se muestra en la sección de ejemplos).
Paso 4) Continúe con el paso 3 hasta que se hayan visitado todos los nodos.

Después de realizar todos estos pasos, encontraremos el camino que cueste lo mínimo desde el origen hasta el destino.

Diferencia entre Dijkstra y BFS, DFS

La principal diferencia entre Dijkstra y BFS-DFS radica en que Dijkstra es un algoritmo de búsqueda de caminos más cortos, mientras que BFS y DFS son algoritmos de búsqueda de caminos de carácter general. En general, BFS y DFS no consideran el costo de las aristas al encontrar el camino. Por lo tanto, estos algoritmos no pueden garantizar el camino más corto.

Demostración en cuadrícula 2D de cómo funciona BFS

algosketch, mostrando demostración de BFS

Esta demostración indica que BFS solo encuentra el camino. Sin embargo, no le importa el peso del camino. BFS (Búsqueda primero en amplitud) supone que viajar de un nodo a otro costará solo 1.

Veamos un ejemplo de gráfico:

Aquí, BFS encuentra un camino en el nivel 2. BFS recorre el grafo en orden de niveles. Por lo tanto, viaja de esta manera:

Paso 1) Comience desde el nodo “1” y visite todos los nodos adyacentes 2, 3, 4.

Paso 2) Marca los nodos 2, 3 y 4 como de nivel 1 y visita sus nodos adyacentes. Continuará explorando todos los nodos adyacentes hasta llegar al nodo de destino.

En términos de DFS, recorrerá la ruta del 1 al 7 de la siguiente manera:

• 1→2→3→7 (Costo original 10, costo DFS 3)
• 1→2→6→7 (Costo original 7, costo DFS 3)
• 1→3→7 (Costo original 8, costo DFS 2)
• 1→4→5→7 (Costo original 13, costo DFS 3)

Como podemos ver, DFS calcula el coste de su ruta con el número de aristas. DFS hace lo siguiente:

• DFS puede encontrar una ruta desde el origen (vértice inicial) hasta el destino.
• No puede garantizar si la ruta descubierta desde el nodo de origen hasta el destino es la ruta más corta o no.

Sin embargo, en lo que respecta al algoritmo de Dijkstra, este elige las aristas en función de su coste. Al ser un algoritmo voraz, seleccionará los caminos de menor coste.

Ejemplo del algoritmo de Dijkstra

El algoritmo de Dijkstra utiliza el costo o el peso para calcular el costo total del camino.

El objetivo del algoritmo de Dijkstra es minimizar este coste o peso total. En el ejemplo que se muestra arriba, encontramos las mejores rutas desde el nodo 1 al nodo 7 y luego calculamos todos los costos.

En el algoritmo de Dijkstra, se encuentran los caminos más cortos calculando pesos. No se buscan todos los caminos posibles. Veamos un ejemplo del algoritmo de Dijkstra. Por ejemplo, se le pide que encuentre el camino más corto del nodo 1 al 7.

Para este proceso, los pasos se detallan a continuación:

Paso 1) Inicializa el costo del nodo inicial a 0. Asigna “Inf” al resto de los nodos. Significa que no existe una ruta entre el origen y el nodo, o que la ruta aún no se ha visitado.

Paso 2) Cuando selecciones el nodo 1, se marcará como visitado. Luego, actualiza todos los vecinos adyacentes del nodo 1. 2, 3 y 4 son los nodos vecinos del nodo 1.

Al actualizar un costo, debemos seguir el procedimiento a continuación:

Podemos actualizar el costo de cada nodo usando la fórmula anterior. Por ejemplo, estábamos en el nodo 1 y necesitábamos actualizar el costo de sus nodos adyacentes 2, 3 y 4. Después de la actualización, los costos se verán así:

Paso 3) Para el nodo “2”, los vecinos son 6 y 3. Actualizamos el costo en “6” comparando el infinito (valor actual) con el costo del nodo 2 más el costo del camino de 2 a 6. En resumen, el nodo “6” tendrá un costo de 1+3, es decir, 4.

El nodo 3 es vecino del nodo 2. Sin embargo, calculamos su costo en el paso anterior, que fue 7. Ahora, si nuestra ruta es 1-2-3, el nodo 3 tendrá un costo de 10. Ruta 1-2- 3 costarán 10, mientras que de 1 a 3 costarán 7.

Paso 4) Para el nodo 3, el nodo vecino es el 7. Por lo tanto, al comparar el valor actual del nodo 7 con el costo del camino (7+1) u 8, actualizamos el costo del nodo 7, que es 8. Así, encontramos un camino del nodo 1 al nodo 7, que es 1→3→7. El costo es 8.

Paso 5) Para el nodo 4, actualizaremos el costo de su nodo adyacente en consecuencia. Por lo tanto, el nodo “5” tendrá un costo actualizado de 8. Después de los pasos 4 y 5, se verá así:

Ahora, el camino 1-3-7 tiene un costo de 8 (anteriormente). El nodo “7” no se marcó como visitado porque podemos llegar a él desde el nodo “6”. El camino “1-2-6” tenía un costo de 4. Por lo tanto, el camino 1-2-6-7 tendrá un costo de 7.

Como 7 < 8, el camino más corto desde el vértice de origen “1” hasta el vértice de destino “7” será 1-2-6-7, y el costo es 7. Anteriormente era 1-3-7, y el costo era 8. Por lo tanto, el grafo final se verá así:

El borde marcado con una línea negra es nuestro camino más corto del 1 al 7, y nos costará 7.

Apodo Code Algoritmo de Dijkstra

Aquí está el pseudocódigo del algoritmo de Dijkstra:

Dijkstra(G, S):
  for each vertex V in G
    distance[V] <- Infinity
    previous[V] <- NULL
    if V does not equal S, then,
      (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
    U <- Extract the MIN from Q
    For each unvisited adjacent V of U
      TotalDistance <- distance[U] + edge_cost(U, V)
      if TotalDistance is less than distance[V], then
        distance[V] <- TotalDistance
        previous[V] <- U
  return distance, previous

C++ Implementación del algoritmo de Dijkstra

Para implementar el algoritmo de Dijkstra usando C++Aquí está el código:

#include <bits/stdc++.h>
using namespace std;
#define size 7
int minimumDistance(int distance[], bool visited[]) {
  int min = INT_MAX;
  int min_index = INT_MAX;
  for (int i = 0; i < size; i++) {
    if (!visited[i] && distance[i] <= min) {
      min = distance[i];
      min_index = i;
    }
  }
  return min_index;
}
void printParentPath(int parent[], int i) {
  if (parent[i] == -1) {
    return;
  }
  printParentPath(parent, parent[i]);
  cout << i + 1 << " ";
}
void dijkstra(int graph[size][size], int source) {
  int distance[size];
  bool visited[size];
  int parent[size];
  for (int i = 0; i < size; i++) {
    parent[0] = -1;
    distance[i] = INT_MAX;
    visited[i] = false;
  }
  distance[source] = 0;
  for (int i = 0; i < size - 1; i++) {
    int U = minimumDistance(distance, visited);
    visited[U] = true;
    for (int j = 0; j < size; j++) {
      int curr_distance = distance[U] + graph[U][j];
      if (!visited[j] && graph[U][j] &&
          curr_distance < distance[j]) {
        parent[j] = U;
        distance[j] = curr_distance;
      }
    }
  }
  cout << "Vertex\t\tDistance\tPath" << endl;
  for (int i = 1; i < size; i++) {
    cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t"
         << source + 1 << " ";
    printParentPath(parent, i);
    cout << endl;
  }
}
int main() {
  int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0},
                           {7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0},
                           {0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3},
                           {0, 0, 0, 0, 5, 3, 0}};
  dijkstra(graph, 0);
}

Salida:

Vertex     Distance        Path

1->2           1             1 2
1->3           7             1 3
1->4           6             1 4
1->5           8             1 4 5
1->6           4             1 2 6
1->7           7             1 2 6 7

Python Implementación del algoritmo de Dijkstra

Para implementar el algoritmo de Dijkstra usando PythonAquí está el código:

num_of_vertex = 7
def minimumDistance(distance, visited):
    _min = 1e11
    min_index = 1e11
    for i in range(num_of_vertex):
        if not visited[i] and distance[i] <= _min:
            _min = distance[i]
            min_index = i
    return min_index

def printParentNode(parent, i):
    if parent[i] == -1:
        return
    printParentNode(parent, parent[i])
    print("{} ".format(i + 1), end="")

def dijkstra(graph, src):
    distance = list()
    visited = list()
    parent = list()
    for i in range(num_of_vertex):
        parent.append(-1)
        distance.append(1e11)
        visited.append(False)
    distance[src] = 0
    for i in range(num_of_vertex - 1):
        U = minimumDistance(distance, visited)
        visited[U] = True
        for j in range(num_of_vertex):
            curr_distance = distance[U] + graph[U][j]
            if not visited[j] and graph[U][j] and curr_distance < distance[j]:
                parent[j] = U
                distance[j] = curr_distance
    print("Vertex\t\tDistance\tPath")
    for i in range(num_of_vertex):
        print("{}->{}\t\t{}\t\t{} ".format(src + 1, i + 1, distance[i], src + 1), end="")
        printParentNode(parent, i)
        print("")

graph = [
    [0, 1, 7, 6, 0, 0, 0],
    [1, 0, 9, 0, 0, 3, 0],
    [7, 9, 0, 0, 0, 0, 1],
    [6, 0, 0, 0, 2, 0, 0],
    [0, 0, 0, 2, 0, 0, 0],
    [0, 3, 0, 0, 0, 0, 3],
    [0, 0, 0, 0, 5, 3, 0]
]
dijkstra(graph, 0)

Salida:

Vertex     Distance        Path

1->1           0              1
1->2           1              1 2
1->3           7              1 3
1->4           6              1 4
1->5           8              1 4 5
1->6           4              1 2 6
1->7           7              1 2 6 7

Podemos observar que el algoritmo calcula la distancia más corta desde el nodo de origen.

Aplicación del algoritmo de Dijkstra

El algoritmo de Dijkstra tiene una amplia gama de aplicaciones. Entre ellas, se utiliza ampliamente en el campo de las redes. A continuación, se presentan algunos ejemplos prácticos del algoritmo de Dijkstra:

Dijkstra en Google Mapas: Este algoritmo es la base para encontrar las rutas más cortas, como podemos ver en el fragmento de código anterior.

Google no utiliza el algoritmo simple de Dijkstra. En su lugar, utiliza una versión modificada. Cuando seleccionas un destino, te muestra múltiples rutas en Google Mapas. Entre estos caminos, algunos se ordenan para el usuario. Estos caminos se seleccionan en función del "tiempo". Por lo tanto, el "tiempo" es un costo de arista para el camino más corto.

Dijkstra en enrutamiento IP: enrutamiento IP El enrutamiento IP es un término de redes que describe cómo se envía un paquete de datos al receptor a través de diferentes rutas. Estas rutas incluyen enrutadores, servidores y otros equipos. En el enrutamiento IP, existen diferentes tipos de protocolos.

Estos protocolos ayudan al enrutador a encontrar las rutas más cortas para enviar los datos. Uno de estos protocolos se llama OSPF (Open Shortest Path First). OSPF utiliza el algoritmo de Dijkstra. El enrutador mantiene una tabla de rutas que comparte con los enrutadores vecinos. Tras recibir la tabla actualizada, deben recalcular todas las rutas. Para ello, el enrutador utiliza el algoritmo de Dijkstra.

Limitación del algoritmo de Dijkstra

El algoritmo de Dijkstra no puede garantizar el camino más corto en un grafo con aristas negativas. El algoritmo de Dijkstra sigue estos principios:

• Se tomará un camino más corto de un nodo a otro.
• Una vez que se selecciona la ruta más corta entre dos nodos, no se volverá a calcular.

Aquí, observe dos ejemplos con aristas negativas.

En el gráfico de la izquierda, Hay tres vértices. El algoritmo de Dijkstra se ejecutará en el grafo de la siguiente manera:

Paso 1) El vértice inicial “1” se inicializará a cero. Los otros nodos tendrán infinito.

Paso 2) Marca el nodo “1” como visitado e inclúyelo en la ruta más corta.

Paso 3) La distancia del nodo de origen 1 a los nodos “2” y “3” se establece en infinito, ya que aún no se ha calculado la ruta más corta. Por lo tanto, cualquier ruta que cueste menos de infinito se añadirá a la ruta más corta (enfoque voraz).

Paso 4) Actualizando la distancia del vértice de origen “1” al “2”. El peso actual será 5 (5 < infinito). De forma similar, actualizando la distancia del nodo “1” al “3” con un peso de 3.

Paso 5) Ahora, si comprobamos las distancias más cortas desde el nodo “1”, encontramos que 5 es la distancia más corta para la arista 1→2. Por lo tanto, el nodo “2” se marcará como visitado. De manera similar, el nodo “3” también se marcará como visitado, ya que la distancia más corta es 3.

Sin embargo, si observamos, existe un camino 1-3-2 que cuesta solo 2. Pero Dijkstra muestra que desde el nodo "1" al nodo "2", la distancia más corta es 5. Por lo tanto, Dijkstra no calculó correctamente la distancia más corta. La razón es que Dijkstra es un algoritmo voraz. Así, una vez que un nodo se marca como visitado, no se vuelve a considerar, aunque pueda haber un camino más corto disponible. Este problema solo ocurre cuando las aristas tienen costos o pesos negativos.

En este escenario, el algoritmo de Dijkstra no logra calcular la ruta más corta entre dos nodos. Por lo tanto, este algoritmo presenta algunas desventajas. Para resolver este problema de aristas negativas, se utiliza otro algoritmo llamado «Algoritmo de Bellman-Ford». Este algoritmo sí puede trabajar con aristas negativas.

Complejidad del algoritmo de Dijkstra

La implementación anterior utilizó dos bucles "for". Estos bucles se ejecutan para la cantidad de vértices. Por lo tanto, la complejidad temporal es O(V²)Aquí, el término “O” es una notación que proporciona una suposición para el algoritmo de Dijkstra.

Podemos almacenar el grafo usando una "cola de prioridad". Una cola de prioridad es una estructura de datos de montón binario. Será más eficiente que una matriz 2D. Una arista con un costo mínimo tendrá una alta prioridad. Entonces la complejidad temporal será O(E log V). Aquí, E es el número de aristas y V es el número de vértices.

La complejidad del espacio es O(V²), ya que estamos usando una matriz de adyacencia (Matriz 2D). La complejidad del espacio se puede optimizar utilizando una lista de adyacencia o una estructura de datos de cola.

Preguntas Frecuentes