Algoritmo de Dijsktra: C++, Python Ejemplo de código
sarah chen
¿Cuál es el camino más corto o la distancia más corta?
Un camino desde el vértice de origen al vértice de destino que cuesta un mínimo 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 a un destino. Entre estas rutas, si hay una ruta que cuesta una cantidad mínima, podemos llamarla algoritmo del camino más corto.
Aquí "Costo" significa la cantidad de nodos en la ruta o la suma de costos en cada ruta. Un camino puede tener uno o varios bordes. La conexión entre dos vértices se llama "borde". Existen varios tipos de algoritmos de ruta más corta, como el algoritmo de Dijkstra, el algoritmo de Bellman-Ford, etc.
Aquí discutimos sobre el algoritmo de Dijkstra.
Veamos el siguiente gráfico ponderado:
- El término "ponderado" significa mover costos de un nodo a otro. Por ejemplo, al pasar del nodo 1 al nodo 2, el costo o peso es 1.
- El camino entre el nodo 1 y el nodo 2 se llama borde.
- "No dirigido" significa que puede mover un nodo a otro y volver al nodo anterior. Entonces, si intentamos encontrar todas las rutas desde el nodo 1 al nodo 7, será:
| Ruta o Camino | Costo |
|---|---|
| 1-2-6-7 | (1+3+3) = 7 |
| 1-2-3-7 | (1+9+1) = 11 |
| 1-3-7 | (7+1) = 8 |
| 1-4-5-7 | (6+2+5) = 13 |
Entre estas cuatro rutas, podemos ver que la primera ruta nos costará 7. Por lo tanto, es el camino más corto en términos de coste.
Cómo funciona el algoritmo de Dijkstra
El algoritmo de Dijkstra puede encontrar la distancia más corta en gráficos ponderados tanto dirigidos como no dirigidos. Este algoritmo es codicioso porque siempre elige el nodo más corto o más cercano al origen. El término "codicioso" significa que entre un conjunto de resultados o resultados, el Algoritmo elegirá el mejor de ellos.
Aquí intentamos 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 destino. Como resultado, se comporta como un algoritmo codicioso.
En la sección de "ejemplo" a continuación, verá el enfoque paso a paso. Funciona de la siguiente manera:
Paso 1) Inicialice el nodo inicial con costos 0 y el resto del nodo como costo infinito.
Paso 2) Mantener una matriz o lista para realizar un seguimiento de los nodos visitados
Paso 3) Actualice el costo del nodo con el costo mínimo. Se puede hacer comparando el costo actual con el costo del camino. (La demostración se muestra en la sección de ejemplo)
Paso 4) Continúe con el paso 3 hasta visitar 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 es que Dijkstra es el algoritmo de búsqueda de ruta más corto y BFS, DFS es el algoritmo de búsqueda de ruta. En casos generales, BFS y DFS no consideran el costo al encontrar el camino. Por tanto, estos algoritmos no pueden garantizar el camino más corto.
Demostración de cuadrícula 2D de cómo funciona 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.
Pero veamos un gráfico de ejemplo:
Aquí, encuentra una ruta en el nivel 2. BFS atraviesa el gráfico en orden de nivel. Entonces, viaja como:
Paso 1) Comience desde el nodo "1" y visite todos los nodos adyacentes 2,3,4
Paso 2) Marque el nodo 2,3,4 como nivel 1 y visite 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 vemos, DFS calcula su costo de ruta con la cantidad de profundidad o la cantidad 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 términos del algoritmo de Dijkstra, elegirá los bordes en función de su costo. Como algoritmo codicioso, elegirá el mejor camino o el de menor costo.
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, encontrará los caminos más cortos calculando pesos. No buscará todos los caminos posibles. Demostremos el algoritmo de Dijkstra con un ejemplo. Por ejemplo, le han pedido que encuentre la ruta más corta desde el nodo 1 al 7.
Para este proceso, los pasos se detallan a continuación:
Paso 1) Inicialice el costo del nodo inicial a 0.
Resto del nodo, asignar “Inf”. Significa que no existe una ruta entre el vértice inicial (la fuente) y el nodo, o que la ruta aún no se ha visitado.
Paso 2) Cuando seleccione el nodo 1, se marcará como visitado. Luego actualice todos los vecinos adyacentes del nodo 1. 2,3,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 su nodo adyacente 2,3,4.
Después de la actualización, el costo o peso se verá así:
Paso 3) Para el nodo "2", los vecinos son 6 y 3. Estamos actualizando el costo en “6” comparando infinito (valor actual). El costo del nodo 2 + costo de ruta de 2 a 6. En pocas palabras, el nodo "6" tendrá el costo de 1+3 o 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 7. Entonces, comparando el valor actual del nodo 7 con el costo de la ruta (7+1) u 8, actualizaremos el costo del nodo 7. Es decir, 8.
Entonces, encontramos un camino desde el nodo 1 al nodo 7, y es 1 → 3 → 7. El costo es 8.
Paso 5) Para el nodo 4, Actualizaremos el costo del nodo adyacente en consecuencia. Entonces, el nodo “5” tendrá un costo actualizado de 8. Después del paso 4,5, se verá así:
Ahora, el camino 1-3-7 tiene el coste de 8 (anteriormente). El nodo "7" no se marcó como visitado porque podemos llegar al nodo "7" desde el nodo "6". El camino “1-2-6” tenía un coste de 4. Entonces el camino 1-2-6-7 tendrá un coste de 7.
Como 7 < 8, es por eso que el camino más corto desde el vértice de origen “1” al 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.
Entonces, el gráfico 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.
Algoritmo de Pseudocódigo Dijkstra
Aquí está el pseudocódigo del algoritmo de Dijkstra.
Dijkstra(G, S):
for each vertex V in G
distance[V] & lt; - Infinity
previous[V] & lt; - NULL
if V does not equal S, then,
(priority queue) Q.push(V)
distance[S] = 0
While Q is not empty
U & lt; - Extract the MIN from Q
For each unvisited adjacent V of U
TotalDistance & lt; - distance[U] + edge_cost(U, V)
if TotalDistance is less than distance[V], then
distance[V] & lt; - TotalDistance
previous[V] & lt; - 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] & amp; & 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] & amp; & graph[U][j] & amp; &
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 pitón, aquí 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] & lt; = _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 & lt;
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 ver que el algoritmo calcula la distancia más corta desde el nodo fuente.
Aplicación del algoritmo de Dijkstra
Dijkstra Algo tiene un amplio conjunto de usos. Entre ellos, se utiliza ampliamente en el campo de las redes. A continuación se muestran algunos de los usos del algoritmo de Dijkstra en la vida real:
Dijkstra en el mapa de Google: Básicamente, este algoritmo es la columna vertebral para encontrar los caminos más cortos. Como podemos ver en el fragmento de código anterior.
Google no utiliza el algoritmo simple de Dijkstra. En cambio, utiliza una versión modificada. Cuando seleccionas un destino, te muestra varias rutas en el mapa de Google. Entre estas rutas, algunas rutas están clasificadas para el usuario. Estos caminos seleccionados se basan en el “tiempo”. Entonces, el “tiempo” es un costo marginal para el camino más corto.
Dijkstra en enrutamiento IP: enrutamiento IP es una terminología de redes. Significa cómo se envía su paquete de datos al receptor a través de diferentes rutas. Estas rutas constan de enrutadores, servidores, etc. 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 los nombres de protocolo es “OSPF (Open Shortest Path First)”. OSPF utiliza el algoritmo Dijkstra. El enrutador mantiene una tabla de rutas. Cada enrutador comparte su tabla con los enrutadores vecinos. Después de recibir la tabla actualizada, deben calcular nuevamente todas las rutas. En ese momento, el enrutador utiliza el algoritmo Dijkstra.
Limitación del algoritmo de Dijkstra
El algoritmo de Dijkstra no puede garantizar el camino más corto en el gráfico de borde negativo. El algoritmo de Dijkstra sigue estas metodologías:
- 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. Dijkstra se ejecutará en el gráfico de la siguiente manera:
Paso 1) El vértice inicial “1” se inicializará a cero. Los otros nodos tendrán infinito.
Paso 2) Marque el nodo "1" como visitado e inclúyalo en la ruta más corta.
Paso 3) La distancia del nodo fuente 1 a los nodos “2” y “3” se establece en infinito, ya que aún no se ha calculado el camino más corto. Por lo tanto, cualquier camino que cueste menos que infinito se agregará al camino más corto (enfoque codicioso).
Paso 4) Actualización de la distancia desde el vértice de origen o el nodo de origen “1” a “2”. El peso actual será 5 (5<infinito). De manera similar, actualice la distancia del nodo "1" al "3" con el peso de 3.
Paso 5) Ahora, si verificamos las distancias más cortas desde el nodo "1", encontramos que 5 es la distancia más corta para el borde 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, hay un camino 1-3-2 que costará solo 2. Pero Dijkstra muestra que del nodo “1” al nodo “2”, la distancia más corta es 5. Entonces, Dijkstra no pudo calcular el camino más corto. distancia correctamente. La razón por la que sucedió es que Dijkstra es un algoritmo codicioso. Por lo tanto, una vez que un nodo se marca como visitado, no se reconsiderará, aunque puede haber una ruta más corta disponible. Este problema solo ocurre cuando los bordes tienen costos negativos o bordes de peso negativos.
Dijkstra no logra calcular el camino más corto entre dos nodos en este escenario. Como resultado, este algoritmo tiene algunos inconvenientes. Para resolver este problema de borde negativo, se utiliza otro algoritmo llamado "Algoritmo Bellman-Ford". Ese algoritmo puede funcionar con bordes negativos.
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(V2). Aquí, el término "0" significa una notación que da una suposición para el algoritmo de Dijkstra.
Podemos almacenar el gráfico usando la "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 ventaja que tendrá un coste mínimo tendrá una alta prioridad.
Entonces la complejidad del tiempo 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(V2), 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.
