Algoritmo de Dijkstra
En el gráfico, hay nodos y bordes. Los nodos son los valores y los bordes son la ruta o las líneas que crean enlaces entre los dos nodos. En Python, podemos implementar los nodos y los bordes utilizando el diccionario anidado. Podemos representar los nodos como una clave y todas las rutas de ese nodo a otros nodos como un valor de esa clave en particular.
El algoritmo de Dijkstra se usa para encontrar la ruta más corta entre el nodo fuente y el nodo de destino. El enfoque de este algoritmo se usa llamado enfoque codicioso. Entonces, en este artículo, vamos a comprender los conceptos del algoritmo de Dijkstra y cómo podemos implementarlo utilizando la programación de Python.
El algoritmo de Dijkstra, como dijimos antes, está utilizando el concepto del enfoque codicioso. Podemos entender el enfoque codicioso en un término normal que encuentra la solución óptima de las opciones disponibles.
Pasos de algoritmo
- Primero inicializamos el valor del nodo de origen 0 y otros valores de nodos adyacentes como infinito.
- Inserte el nodo fuente y el valor de distancia como un par en el diccionario. Por ejemplo, el par de valor de nodo de origen será . El S representa el nombre del nodo y 0 es el valor de distancia. El valor 0 es porque inicializamos el valor del nodo de origen 0.
- El lazo continuará hasta el diccionario, no nulo (o no vacío).
- Asignamos cualquier par desde el diccionario a Current_Source_Node basado en la siguiente condición:
El valor de distancia del nodo debe ser menor que los valores de distancia entre los nodos disponibles. Después de eso, elimine eso de la lista del diccionario porque eso ahora es actual_source_node.
- Para cada adyacent_link_node a la actualidad
- Si (DIST [adjacent_link_node]> valor de borde de current_source_node al nodo adyacente+ DIST [Current_source_node])
- Dist [adjacent_link_node] = valor de borde de current_source_node al nodo adyacente + DIST [Current_Source_Node]
- Luego actualice el diccionario con par
Pasos de algoritmo de Dijkstra
El algoritmo de Dijkstra se usa para encontrar la ruta más corta entre el nodo fuente y el nodo de destino.
Paso 1: Para esto, primero tenemos que inicializar el nodo fuente como un 0 y otros nodos como ∞. Luego insertamos el par en el diccionario. Nuestro primer par será porque la distancia desde la fuente a la fuente en sí es 0 como se muestra en el gráfico y la tabla a continuación.
| Nodo fuente | Nodo de destino | Dist desde el nodo fuente | Diccionario |
|---|---|---|---|
| 0 | 0 | 0 | [0, 0] |
| 0 | 1 | ∞ | |
| 0 | 2 | ∞ | |
| 0 | 3 | ∞ | |
| 0 | 4 | ∞ | |
| 0 | 5 | ∞ |
Paso 2 En el diccionario, solo hay un par . Por lo tanto, tomamos esto como un Current_Source_Node y relajamos el peso de los bordes de todos los nodos adyacentes del Current_Source_Node (0).
| nodo fuente actual | Nodo adyacente | Dist de la fuente (0) al nodo adyacente | Actualizar el peso de EGDE o no |
|---|---|---|---|
| 0 | 1 | dist [1] = ∞ | Dist [1]> Dist_between [0 - 1] + Dist [0] I.e ∞> 5 + 0 Entonces, vamos a actualizar la distancia. Actualizar dist => Dist [1] = 5 y actualizar el par en el dict |
| 0 | 2 | dist [2] = ∞ | Dist [2]> Dist_between [0 - 2] + Distancia [0] I.e ∞> 1 + 0 Entonces, vamos a actualizar la distancia. Actualizar dist => Dist [2] = 1 y actualizar el par en el dict |
| 0 | 3 | dist [3] = ∞ | Dist [3]> Dist_between [0 - 3] + Dist [0] Entonces, vamos a actualizar la distancia. i.E ∞> 4 + 0 Actualización Dist, i.mi Dist [3] = 4 y actualizar el par en el dict |
| Nodo fuente | Nodo de destino | Dist desde el nodo fuente | Diccionario |
|---|---|---|---|
| 0 | 0 | 0 | [15] [2, 1] [3, 4] |
| 0 | 1 | 5 | |
| 0 | 2 | 1 | |
| 0 | 3 | 4 | |
| 0 | 4 | ∞ | |
| 0 | 5 | ∞ |
Paso 3: Ahora, eliminamos el siguiente par del diccionario para el actual_source_node. Pero la condición es que tenemos que elegir el nodo de valor de distancia mínima. Por lo tanto, elegimos el Diccionario y asignado como un Current_Source_Node y relajamos el peso de los bordes de todos los nodos adyacentes del Current_Source_Node (2).
| nodo fuente actual | Nodo adyacente | Dist de la fuente (0) al nodo adyacente | Actualizar el peso de EGDE o no |
|---|---|---|---|
| 2 | 0 | distancia [0] = 0 | Dist [0] < dist_between [ 2 - 0 ] + dist [ 2 ] i.e 0 dist_between [ 2 - 1 ] + dist [ 2 ] i.e 5 > 3 + 1 |
| 2 | 1 | distancia [1] = 5 | Entonces, vamos a actualizar la distancia. Actualizar dist ==> dist [1] = 4 y actualice el par en el Dict Dist [3]> Dist_between [2 - 3] + Dist [2] I.E 4> 2 + 1 |
| 2 | 3 | distancia [3] = 4 | Entonces, vamos a actualizar la distancia. Actualizar dist => dist [3] = 3 y actualice el par en el Dict Dist [4]> Dist_between [2 - 4] + Dist [2] I.e ∞> 1 + 1 |
| 2 | 4 | distancia [4] = ∞ | Entonces, vamos a actualizar la distancia. Actualizar dist => Dist [4] = 2 Actualizar el par en el dict |
| Nodo fuente | Nodo de destino | Dist desde el nodo fuente | Diccionario |
|---|---|---|---|
| 2 | 0 | 0 | [1, 4] [3, 3] [4, 2] |
| 2 | 1 | 4 | |
| 2 | 2 | 1 | |
| 2 | 3 | 3 | |
| 2 | 4 | 2 | |
| 2 | 5 | ∞ |
Etapa 4: Ahora, eliminamos el siguiente par del diccionario para elegir Current_Source_Node y relajar el peso de los bordes de todos los nodos adyacentes del Current_Source_Node (4).
| nodo fuente actual | Nodo adyacente | Dist de la fuente (0) al nodo adyacente | Actualizar el peso de EGDE o no |
|---|---|---|---|
| 4 | 1 | Dist [1] = 4 | Dist [1] < dist_between [ 4 - 1 ] + dist [ 4 ] i.e 4 < 8 + 2 No weight updation required. |
| 4 | 2 | Dist [2] = 1 | Dist [2] < dist_between [ 4 - 2 ] + dist [ 4 ] i.e 1 < 1 + 2 No weight updation required. |
| 4 | 3 | Dist [3] = 3 | Dist [3] < dist_between [ 4 - 3 ] + dist [ 4 ] i.e 3 < 2 + 2 No weight updation required. |
| 4 | 5 | dist [5] = ∞ | Entonces, vamos a actualizar la distancia. Actualizar dist => dist [5] = 5 Actualizar el par en el dict |
| Nodo fuente | Nodo de destino | Dist desde el nodo fuente | Diccionario |
|---|---|---|---|
| 4 | 0 | 0 | [1, 4] [3, 3] [5, 5] |
| 4 | 1 | 4 | |
| 4 | 2 | 1 | |
| 4 | 3 | 3 | |
| 4 | 4 | 2 | |
| 4 | 5 | 5 |
Paso 5: Eliminamos el siguiente par del diccionario para elegir Current_Source_Node y relajamos el peso de los bordes de todos los nodos adyacentes del Current_Source_Node (3).
| nodo fuente actual | Nodo adyacente | Dist de la fuente (0) al nodo adyacente | Actualizar el peso de EGDE o no |
|---|---|---|---|
| 3 | 0 | Dist [0] = 0 | Dist [0] < dist_between [ 3 - 0 ] + dist [ 3 ] i.e 0 < 4 + 3 No weight updation required. |
| 3 | 2 | Dist [2] = 1 | Dist [2] < dist_between [ 3 - 2 ] + dist [ 3 ] i.e 1 < 2 + 3 No weight updation required. |
| 3 | 4 | Dist [4] = 2 | Dist [4] < dist_between [ 3 - 4 ] + dist [ 3 ] i.e 2 < 2 + 3 No weight updation required. |
| 3 | 5 | Dist [5] = 5 | Entonces, vamos a actualizar la distancia. Actualizar dist =>Dist [5] = 4 Actualizar el par en el dict |
| Nodo fuente | Nodo de destino | Dist desde el nodo fuente | Diccionario |
|---|---|---|---|
| 3 | 0 | 0 | [1, 4] [5, 4] |
| 3 | 1 | 4 | |
| 3 | 2 | 1 | |
| 3 | 3 | 3 | |
| 3 | 4 | 2 | |
| 3 | 5 | 4 |
Paso 6: Eliminamos el siguiente par del diccionario para elegir Current_Source_Node y relajamos el peso de los bordes de todos los nodos adyacentes del Current_Source_Node (1).
| nodo fuente actual | Nodo adyacente | Dist de la fuente (0) al nodo adyacente | Actualizar el peso de EGDE o no |
|---|---|---|---|
| 1 | 0 | Dist [0] = 0 | distancia [0] < distance_between [ 1 - 0 ] + distance [ 1 ] i.e Since 0 < 5 + 4 No weight updation required. |
| 1 | 2 | Dist [2] = 1 | Dist [2] < dist_between [ 1 - 2 ] + dist [ 1 ] i.e 1 < 3 + 4 No weight updation required. |
| 1 | 4 | Dist [4] = 2 | Dist [4] < dist_between [ 1 - 4 ] + dist [ 1 ] i.e 2 < 8 + 4 No weight updation required. |
| Nodo fuente | Nodo de destino | Dist desde el nodo fuente | Diccionario |
|---|---|---|---|
| 1 | 0 | 0 | [5, 4] |
| 1 | 1 | 4 | |
| 1 | 2 | 1 | |
| 1 | 3 | 3 | |
| 1 | 4 | 2 | |
| 1 | 5 | 4 |
Paso 7: Ahora, eliminamos el siguiente par del diccionario para elegir Current_Source_Node y relajar el peso de los bordes de todos los nodos adyacentes del Current_Source_Node (5).
| nodo fuente actual | Nodo adyacente | Dist de la fuente (0) al nodo adyacente | Actualizar el peso de EGDE o no |
|---|---|---|---|
| 5 | 3 | Dist [3] = 3 | ddist [3] < dist_between [ 5 - 3 ] + dist [ 5 ] i.e 3 < 1 + 4 No weight updation required. |
| 5 | 4 | Dist [4] = 2 | Dist [4] < dist_between [ 5 - 4 ] + dist [ 5 ] i.e 2 < 3 + 4 No weight updation required. |
Ahora, el diccionario es nulo y no queda ningún par. Entonces, nuestro algoritmo ahora se detiene. Y obtuvimos toda la ruta más corta desde los nodos de origen principal hasta todos los nodos de los demás como se muestra a continuación:
| Nodo fuente | Nodo de destino | Dist desde el nodo fuente | Diccionario |
|---|---|---|---|
| 0 | 0 | 0 | |
| 0 | 1 | 4 | |
| 0 | 2 | 1 | |
| 0 | 3 | 3 | |
| 0 | 4 | 2 | |
| 0 | 5 | 4 |
Código de Python: A continuación se muestra la implementación del algoritmo anterior.
1 # Algoritmo de Dijkstra en Python2 de las colecciones importar predeterminado
3
4 class node_dist:
5 def __init __ (self, nombre, dist):
6 yo.nombre = nombre
7 yo.dist = dist
8
9 clase Dijksstraalgorithm:
10
11 def __init __ (self, node_count):
12 yo.adyacentList = defaultDict (lista)
13 yo.node_count = node_count
14
15 DEF adjacent_nodelist (self, src, node_dist):
16 yo.adyacentList [SRC].append (node_dist)
17
18 def dijstras_shortest_path (self, source_node):
19 # Inicializar los nodos con valor infinito y fuente
20 # nodo con 0
21 Dist = [999999999999] * Self.nodo_count
22 DIST [Source_Node] = 0
23
24 # Estamos creando un dict como se dice en el algritmo con el
25 # par de valor
26 dict_of_node_dist = fuente_node: 0
27
28 Mientras que dict_of_node_dist:
29
30 # Ahora, vamos a asaltar un par de un
31 # curtent_source_node pero condiciona ese valor dist
32 # debería ser el valor mínimo
33 Current_source_node = min (dict_of_node_dist,
34 clave = lambda k: dict_of_node_dist [k])
35
36 # después de asignar ese par a la actual_source_node,
37 # Eliminar ese artículo del dict
38 del dict_of_node_dist [curtent_source_node]
39
40 para node_dist en uno mismo.adyacentList [current_source_node]:
41 adjacentNode = node_dist.nombre
42 Source_to_adjacentnode_dist = node_dist.distrito
43
44 # Estamos haciendo aquí la relajación de la ventaja del nodo adyacente
45 if dist [adjacentNode]> Dist [current_source_node] + \
46 Source_to_adjacentNode_Dist:
47 DIST [adjacentNode] = DIST [Current_Source_Node] + \
48 Source_To_adJacentNode_Dist
49 DICT_OF_NODE_DIST [adjacentNode] = Dist [adyacentNode]
50
51 para i en el rango (yo mismo.node_count):
52 imprime ("Distancia desde el nodo fuente ("+str (fuente_node)+") => a"
53 "Nodo de destino (" + str (i) + ") =>" + str (dist [i]))
54
55 Def Main ():
56
57 gráfico = Dijkstraalgorithm (6)
58 gráfico.Adyacent_nodelist (0, node_dist (1, 5))
59 gráfico.Adyacent_nodelist (0, node_dist (2, 1))
60 gráficos.Adyacent_nodelist (0, node_dist (3, 4))
61
62 gráfico.Adyacent_nodelist (1, node_dist (0, 5))
63 gráfico.Adyacent_nodelist (1, node_dist (2, 3))
64 gráfico.Adyacent_nodelist (1, node_dist (4, 8))
sesenta y cinco
66 gráfico.Adyacent_nodelist (2, node_dist (0, 1))
67 gráfico.Adyacent_nodelist (2, node_dist (1, 3))
68 gráfico.Adyacent_nodelist (2, node_dist (3, 2))
69 gráfico.Adyacent_nodelist (2, node_dist (4, 1))
70
71 gráfico.Adyacent_nodelist (3, node_dist (0, 4))
72 gráfico.Adyacent_nodelist (3, node_dist (2, 2))
73 gráfico.Adyacent_nodelist (3, node_dist (4, 2))
74 gráfico.Adyacent_nodelist (3, node_dist (5, 1))
75
76 gráfico.Adyacent_nodelist (4, node_dist (1, 8))
77 gráfico.Adyacent_nodelist (4, node_dist (2, 1))
78 gráfico.Adyacent_nodelist (4, node_dist (3, 2))
79 gráfico.Adyacent_nodelist (4, node_dist (5, 3))
80
81 gráfico.Adyacent_nodelist (5, node_dist (3, 1))
82 gráfico.Adyacent_nodelist (5, node_dist (4, 3))
83
84 gráfico.Dijkstras_shortest_path (0)
85
86
87 si __name__ == "__main__":
88 Main ()
Línea 9 a 53: La explicación de esta clase se da a continuación:
Línea 9: Creamos una clase el nombre Dijkstraalgorithm.
Línea 11 a 16: Inicializamos el adjacentList y Node_Count. El adyacentList es un dicte que usamos para almacenar el nodo y todos sus nodos adyacentes, como el nodo 0: . Este código si imprime, mostrará el resultado como a continuación:
Defaultdict (Defaultdict (
El resultado anterior muestra que estamos creando un dict que tiene todos los detalles de un nodo particular y sus nodos adyacentes.
Línea 21 a 22: Inicializamos todos los nodos con un valor infinito y nodos de origen con 0 según nuestro algoritmo.
Línea 26: Inicializamos el dict_of_node_dist según nuestro algoritmo, que es nuestro primer par.
Línea 28 a 50: Implementamos según las líneas de algoritmo 4 a 8.
Línea 57 a 83: Creamos un objeto de la clase Dijksstraalgorithm y pasamos el número de nodos en el gráfico. Luego llamamos al método adjacente_nodelist usando el gráfico de objeto para hacer un dict de todos los nodos con sus nodos adyacentes. El nodo será la clave y los nodos adyacentes y la distancia serán sus valores.
Línea 83: Llamamos al método dijkstras_shortest_path (0) usando el gráfico de objeto.
Producción: Algoritmo de Python Dijkstra.py
- Distancia desde el nodo fuente (0) => al nodo de destino (0) => 0
- Distancia desde el nodo fuente (0) => al nodo de destino (1) => 4
- Distancia desde el nodo fuente (0) => al nodo de destino (2) => 1
- Distancia desde el nodo fuente (0) => al nodo de destino (3) => 3
- Distancia desde el nodo fuente (0) => al nodo de destino (4) => 2
- Distancia desde el nodo fuente (0) => al nodo de destino (5) => 4
Conclusión
En este artículo, hemos estudiado el algoritmo de Dijkstra paso a paso. También hemos estudiado la idea de enfoque codicioso. No incluimos los detalles sobre el enfoque codicioso porque volveremos a este tema (enfoque codicioso) más tarde pronto.
El código de este artículo está disponible en el enlace GitHub:
https: // github.com/shekharpandey89/dijkstra-s-algorithm