Las operaciones de transferencia de datos son un aspecto crucial en el caso de redes y enrutamiento. Por lo tanto, las operaciones de transferencia de datos eficientes son una necesidad, con el mínimo costo de hardware (cables ópticos, componentes de red WDM, decodificadores, multiplexores) y también en el mínimo tiempo posible. Por lo tanto, la necesidad es proponer un algoritmo que encuentre el camino más corto entre dos Nodes (Node de origen y Node de destino). Veamos un algoritmo completamente nuevo a diferencia del Camino más corto de Dijkstra o cualquier otro algoritmo para encontrar el Camino más corto. Dado un gráfico y dos Nodes (Node de origen y Node de destino), encuentre el camino más corto entre ellos. 
Calculemos la relación de distancia para cada enlace:
Distancia del enlace AB [indicada por d(AB)] = 10 Distancia del enlace AC [indicada por d(AC)] = 12 Para el enlace AB , Relación de distancia de AB = d(AB) / (d(AB) + d( AC)) Para enlace AC , relación de distancia de AC = d(AC) / (d(AB) + d(AC))
Algoritmo:
Given a graph and two nodes - 1. Find all the paths connecting the two nodes. 2. For each path calculate probability = (Distance Ratio). 3. After looping over all such paths, find the path for which the probability turns out to be minimum.
Ejemplos:
Input :
Output : Shortest Path is [A -> B]
Explanation :
All possible paths are
P1 = [A->B]
P2 = [A->C->B]
P3 = [A->D->B]
total distance D = d(P1) + d(P2) + d(P3)
= (3) + (2 + 5) + (4 + 3)
= 17
distance ratio for P1 = d(P1) / D = 3/17
distance ratio for P2 = d(P2) / D = 7/17
distance ratio for P3 = d(P3) / D = 7/17
So the shortest path is P1 = [A->B]
Input :
Output : Shortest Path is [A -> B]
Ilustremos el algoritmo con una red de 7 Nodes y descubramos la ruta probabilística más corta entre el Node 1 y el Node 5. 
A continuación se muestra la implementación:
Python3
# Python program to find Probabilistic
# shortest path routing algorithm for
# optical networks
# importing random module
import random
# Number of nodes
NODES = 7
# very small invalid
# when no link exists
INVALID = 0.001
distance_links = [[INVALID for i in range(NODES)]
for j in range(NODES)]
# distance of each link
distance_links[0][1] = 7
distance_links[1][0] = 7
distance_links[1][2] = 8
distance_links[2][1] = 8
distance_links[0][2] = 9
distance_links[2][0] = 9
distance_links[3][0] = 9
distance_links[0][3] = 9
distance_links[4][3] = 4
distance_links[3][4] = 4
distance_links[5][4] = 6
distance_links[4][5] = 6
distance_links[5][2] = 4
distance_links[2][5] = 4
distance_links[4][6] = 8
distance_links[6][4] = 8
distance_links[0][6] = 5
distance_links[6][0] = 5
# Finds next node from current node
def next_node(s):
nxt = []
for i in range(NODES):
if(distance_links[s][i] != INVALID):
nxt.append(i)
return nxt
# Find simple paths for each
def find_simple_paths(start, end):
visited = set()
visited.add(start)
nodestack = list()
indexstack = list()
current = start
i = 0
while True:
# get a list of the neighbors
# of the current node
neighbors = next_node(current)
# Find the next unvisited neighbor
# of this node, if any
while i < len(neighbors) and neighbors[i] in visited:
i += 1
if i >= len(neighbors):
visited.remove(current)
if len(nodestack) < 1:
break
current = nodestack.pop()
i = indexstack.pop()
elif neighbors[i] == end:
yield nodestack + [current, end]
i += 1
else:
nodestack.append(current)
indexstack.append(i + 1)
visited.add(neighbors[i])
current = neighbors[i]
i = 0
# Find the shortest path
def solution(sour, dest):
block = 0
l = []
for path in find_simple_paths(sour, dest):
l.append(path)
k = 0
for i in range(len(l)):
su = 0
for j in range(1, len(l[i])):
su += (distance_links[l[i][j-1]]
[l[i][j]])
k += su
# print k
dist_prob = []
probability = []
for i in range(len(l)):
s, su = 0, 0
for j in range(1, len(l[i])):
su += (distance_links[l[i][j-1]]
[l[i][j]])
dist_prob.append(su/(1.0 * k))
for m in range(len(dist_prob)):
z = (dist_prob[m])
probability.append(z)
for i in range(len(probability)):
if(probability[i] == min(probability)):
z = l[i]
print("Shortest Path is", end = " ")
print(z)
# Driver Code
if __name__ == '__main__' :
source, dest = 1, 5
# Calling the solution function
solution(source, dest)
Producción :
Shortest Path is [1, 2, 5]
Ventaja sobre los algoritmos de ruta más corta comunes: la mayoría de los algoritmos de ruta más corta son algoritmos codiciosos. Por lo tanto, se basa en el hecho de que una solución óptima conduce a una solución globalmente óptima. En la mayoría de los casos, debido a la propiedad codiciosa, es posible que no siempre conduzca a una solución óptima. Pero usando este algoritmo, siempre se puede garantizar una solución óptima y, por lo tanto, la precisión es del 100 %.
Publicación traducida automáticamente
Artículo escrito por Prateek Chanda y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA