El famoso algoritmo de Dijkstra se puede usar en una variedad de contextos, incluso como un medio para encontrar la ruta más corta entre dos enrutadores, también conocido como enrutamiento de estado de enlace . Este artículo explica una simulación del algoritmo de Dijkstra en la que los Nodes (enrutadores) son terminales.
Una vez que se calcula la ruta más corta entre dos Nodes (terminales), la ruta más corta en sí misma se envía como un mensaje a cada terminal en su ruta en secuencia, hasta que se alcanza la terminal de destino. Cada vez que el mensaje ha atravesado un Node, su terminal muestra el recorrido. De esta manera, es posible ver y simular el paso de un mensaje a través de una ruta calculada más corta.
El procedimiento para ejecutar el siguiente código es el siguiente:
- Ejecutar el código del controlador
- Antes de proporcionar cualquier entrada al código del controlador, ejecute los códigos del enrutador router1.py, router2.py, etc. en terminales/pestañas separadas.
- Ahora proporcione la entrada al código del controlador en forma de una array G, en la que cualquier entrada
G[i, j]es la distancia desde el Node i al Node j. La array debe ser simétrica. Si i=j, entoncesD[i, j]=0como la distancia entre un Node y sí mismo se considera que es nada. Si no hay conexión directa entre dos Nodes, entoncesD[i, j]=999(el equivalente de infinito).- Especifique los Nodes de origen y destino, donde los Nodes varían de 0 a 3 y representan los terminales 1 a 4 respectivamente.
Esta implementación especifica cuatro Nodes, pero esto se puede extender fácilmente a N Nodes con N terminales y números de puerto que representan los procesos que se ejecutan en ellos, respectivamente.
Considere el siguiente ejemplo de una red de cuatro Nodes, con las distancias entre ellos especificadas y los Nodes numerados del 0 al 3 de izquierda a derecha:
Distancias entre terminales
Para esta red, la array G con entradas G[i, j] como se especifica arriba sería:
[[0, 1, 999, 999], [1, 0, 2, 999], [999, 2, 0, 3], [999, 999, 3, 0]]
Esta array tendría que introducirse en el código del controlador. El algoritmo de Dijkstra se utiliza para encontrar el camino más corto entre el origen y el destino. Se envía una lista que contiene la ruta restante a cada Node en ruta hacia el destino final.
La implementación en Python se especifica a continuación.
# Driver Code for implementing Dijkstra's algorithm
import socket
import sys
import pickle
S = set()
G =[] # adjacency matrix
# give input matrix
for i in range(4):
listo =[0, 0, 0, 0]
for j in range(4):
listo[j]= int(input("give input"))
G.append(listo)
source = int(input("give source"))
destination = int(input("give destination"))
Q =[] # empty queue
for i in range(4):
Q.append(i)
d =[0, 0, 0, 0] # initialize d values
pi =[0, 0, 0, 0] # initialize pi values
for i in range(4):
if(i == source):
d[i]= 0
else:
d[i]= 999
for i in range(4):
pi[i]= 9000
S.add(source)
# While items still exist in Q
while (len(Q)!= 0):
# Find the minimum distance x from
# source of all nodes in Q
x = min(d[q] for q in Q)
u = 0
for q in Q:
if(d[q]== x):
# Find the node u in Q with minimum
# distance x from source
u = q
print(u, "Is the minimum distance")
Q.remove(u) # removed the minimum vertex
S.add(u)
adj =[]
for y in range(4):
# find adjacent vertices to minimum vertex
if(y != u and G[u][y]!= 999):
adj.append(y)
# For each adjacent vertex, perform the update
# of distance and pi vectors
for v in adj:
if(d[v]>(d[u]+G[u][v])):
d[v]= d[u]+G[u][v]
pi[v]= u # update adjacents distance and pi
route =[]
x = destination
# If destination is source, then pi[x]= 9000.
if(pi[x]== 9000):
print(source)
else:
# Find the path from destination to source
while(pi[x]!= 9000):
route.append(x)
x = pi[x]
route.reverse()
print(route) # Display the route
print(pi) # Display the path vector
print(d) # Display the distance of each node from source
'''We will now send the calculated minimal route to the terminal
# representing 'source'. From the source terminal, the 'route' list
# will be sent to the next hop en route to the final destination.
# At each intermediate terminal, the router removes its own identity
from the list and sends the rest of the route to the next router.
This continues until the final router is reached.'''
sendingroute = pickle.dumps(route)
sockets =[8895, 8896, 8897, 8898]
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect((socket.gethostname(), sockets))
try:
# try sendall if it doesn't work.
sock.send(sendingroute)
finally:
print("")
sock.close()
# Code for Router 1
import socket
import sys
import pickle
for i in range(1) :
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.bind((socket.gethostname(), 8895))
sock.listen(1)
connection, client_address = sock.accept()
route =[]
sockets =[8895, 8896, 8897, 8898]
while 1:
try:
route = pickle.loads(connection.recv(1024))
except EOFError:
break
finally:
break
print("Traversed 1")
socknext = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
if(len(route)>0):
x = route[0]
route.remove(x)
dataroute = pickle.dumps(route)
socknext.connect((socket.gethostname(), sockets[x]))
try:
socknext.send(dataroute) # try sendall
data = socknext.recv(16)
print(data)
finally:
print("")
socknext.close()
# Code for Router 2
import socket
import sys
import pickle
for i in range(1) :
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.bind((socket.gethostname(), 8896))
sock.listen(1)
connection, client_address = sock.accept()
route =[]
sockets =[8895, 8896, 8897, 8898]
while 1:
try:
route = pickle.loads(connection.recv(1024))
except EOFError:
break
finally:
break
print("Traversed 2")
socknext = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
if(len(route)>0):
x = route[0]
route.remove(x)
dataroute = pickle.dumps(route)
socknext.connect((socket.gethostname(), sockets[x]))
try:
socknext.send(dataroute) # try sendall
data = socknext.recv(16)
print(data)
finally:
print("")
socknext.close()
# Code for Router 3
import socket
import sys
import pickle
for i in range(1) :
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.bind((socket.gethostname(), 8897))
sock.listen(1)
connection, client_address = sock.accept()
route =[]
sockets =[8895, 8896, 8897, 8898]
while 1:
try:
route = pickle.loads(connection.recv(1024))
except EOFError:
break
finally:
break
print("Traversed 3")
socknext = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
if(len(route)>0):
x = route[0]
route.remove(x)
dataroute = pickle.dumps(route)
socknext.connect((socket.gethostname(), sockets[x]))
try:
socknext.send(dataroute) # try sendall
data = socknext.recv(16)
print(data)
finally:
print("")
socknext.close()
# Code for Router 4
import socket
import sys
import pickle
for i in range(1) :
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.bind((socket.gethostname(), 8898))
sock.listen(1)
connection, client_address = sock.accept()
route =[]
sockets =[8895, 8896, 8897, 8898]
while 1:
try:
route = pickle.loads(connection.recv(1024))
except EOFError:
break
finally:
break
print("Traversed 4")
socknext = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
if(len(route)>0):
x = route[0]
route.remove(x)
dataroute = pickle.dumps(route)
socknext.connect((socket.gethostname(), sockets[x]))
try:
socknext.send(dataroute) # try sendall
data = socknext.recv(16)
print(data)
finally:
print("")
socknext.close()
Salida Dijkstra
Salida terminal –
Salida terminal
¿Escribir código en un comentario? Utilice ide.geeksforgeeks.org , genere un enlace y compártalo aquí.
Publicación traducida automáticamente
Artículo escrito por RenukaNarayanan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA