Algoritmo de Dijkstra
Antes de enumerar la aplicación en tiempo real del algoritmo de Dijkstra, quiero discutir el mito al respecto. El algoritmo de Dijkstra es un algoritmo codicioso bien conocido y también es un error, porque Dijkstra se utiliza para calcular la distancia más corta desde el nodo fuente a todos los nodos. Almacena el resultado anterior para calcular el resultado final. Por lo tanto, no es un algoritmo codicioso, es un enfoque dinámico para encontrar una solución óptima a nivel mundial eligiendo con avidez una solución óptima a nivel local.
- ¿Qué tan complejo debe ser un algoritmo criptográfico para estar sujeto a las regulaciones de exportación de criptografía?
- ¿Qué es un algoritmo eficiente para encontrar una isla de 1s conectados en una matriz de 0s y 1s?
- ¿Cómo usamos la función de crecimiento de un algoritmo para determinar su orden?
- ¿Existen algoritmos que puedan determinar la convergencia o la falta de ella para cualquier serie arbitraria que se pueda expresar en notación de suma estándar?
- ¿Cuál es la lógica detrás del algoritmo de escaneo de Graham para casco convexo?
Este archivo de imagen GIF muestra cómo funciona realmente para calcular la distancia más corta desde el origen a todos los nodos.
Código de Python para el algoritmo de Dijkstra
Gráfico de clase:
@classmethod
def minDis (cls, ruta, visitado):
dis = float (‘inf’)
para i en rango (0, len (ruta)):
si no se visita [i] y ruta [i] <= dis:
dis = ruta [i]
desindexar = i
volver desindexar
@classmethod
def print_path (cls, ruta):
para i en rango (0, len (ruta)):
print (ruta [i], end = ”)
@classmethod def dijkstra (cls, graph, src):
ruta = [flotante (‘inf’)] * len (gráfico)
visitado = [Falso] * len (gráfico)
ruta [src] = 0
para recuento en rango (0, len (gráfico) -1):
u = cls.minDis (ruta, visitada)
visitado [u] = Verdadero
para v en rango (0, len (gráfico)):
si no se visitó [v] y gráfico [u] [v]! = 0 y ruta [u] + gráfico [u] [v] <ruta [v]:
ruta [v] = gráfico [u] [v] + ruta [u]
cls.print_path (ruta)
gráfico = []
graph.append ([0, 4, 0, 0, 0, 0, 0, 8, 0])
graph.append ([4, 0, 8, 0, 0, 0, 0, 11, 0])
graph.append ([0, 8, 0, 7, 0, 4, 0, 0, 2])
graph.append ([0, 0, 7, 0, 9, 14, 0, 0, 0])
graph.append ([0, 0, 0, 9, 0, 10, 0, 0, 0])
graph.append ([0, 0, 4, 14, 10, 0, 2, 0, 0])
graph.append ([0, 0, 0, 0, 0, 2, 0, 1, 6])
graph.append ([8, 11, 0, 0, 0, 0, 1, 0, 7])
graph.append ([0, 0, 2, 0, 0, 0, 6, 7, 0])
Graph.dijkstra (gráfico, 0)
Este es el gráfico en el que se implementa el código anterior asumiendo ‘0’ como el nodo fuente.
De la línea 25 del código, está claro que el Algoritmo de Dijkstra sigue mirando su resultado anterior. Entonces, es un algoritmo dinámico.
Aplicación en tiempo real del algoritmo de Dijkstra
Ahora creo que estamos listos para conocer su implementación.
- Cualquier SIG (Sistema de Información Geográfica), que necesita determinar la ruta más corta desde el punto A al punto B en un mapa de ruta (un gráfico ponderado en realidad), puede hacer un buen uso del algoritmo de ruta más corta de Dijkstra, tal vez con algunos ajustes y modificaciones.
Ej: Google Map - En redes, la mejor manera de mover los paquetes a un nodo
