Dijkstra

📖

El algoritmo de Dijkstra es un algoritmo de búsqueda de camino más corto utilizado para encontrar la ruta más corta desde un nodo de origen a todos los demás nodos en un grafo ponderado, dirigido o no dirigido, con pesos no negativos

ℹ️

Pasos

Inicialización
Array de distancias, desde infinito
Conjunto de visitados
Bolsa de nodos_previos o también puede contener la arista con la que se visitó el nodo
Inicializar la distancia en el array de distancias del nodo inicial a 0

Bucle iterativo
Se ejecuta la función de selección para obtener el siguiente nodo a visitar
Si el nodo es None saldremos del bucle
Se marca como visitado
Se actualiza el array de distancias. Si la suma de: El valor en el array de distancias más el peso de la arista es menor que la distancia actualmente almacenada en el array. Entonces:
Se actualiza la nueva mejor distancia
Se actualiza el valor en la bolsa de nodos previos

Función de selección

Se deberá seleccionar el nodo no visitado que tenga el valor más bajo en el array de distancias

💡

Este algoritmo es parecido a prim, salvo que en prim, el resultado es un ARM idéntico sin importar el nodo de inicio, mientras que dijkstra genera un arbol diferente dependiendo del nodo de inicio.

La diferencia radica en el criterio de selección:

En prim la distancia a un nodo se mide respencto de cualquier nodo de los ya visitados

En dijkstra la distancia a un nodo se mide desde nodo inicial

Esto supone que el siguiente nodo a visitar no sea el mismo dependiendo del algoritmo que estemos utilizando

#######################################################################
# Dijkstra algorithm for shortest path to all nodes from a given node #
#######################################################################

def getBest(distance, visited):
    """
    This function will return the best node based on the distance and the visited list.
    """
    minDist = float('inf')
    bestNode = None
    
    # Loop over all the nodes
    for i in range(len(distance)):
        # If the node is not visited and the distance is less than the minimum distance, update the best node
        if not visited[i] and distance[i] < minDist:
            bestNode = i
            minDist = distance[i]
        
    # If there is no best node, return None
    return bestNode
    

def dijkstra(g, currentNode):
    """
    Dijkstra algorithm
    Given a graph, represented as a list of tuples, where each tuple is (src, dest, weight).
    This function will return minimum distances from the initial node to all the other nodes.
    """
    n = len(g)
    distances = [float("inf")] * n
    visited = [False] * n
    prevs = [None] * n
    
    # Initial node
    distances[currentNode] = 0

    # Greedy loop
    while True:
        # Get the best candidate (factible, no loops) and update the solution
        currentNode = getBest(distances, visited)
        
        # Exit condition
        if currentNode is None:
            break
        
        # Update visited and new minimum distances
        visited[currentNode] = True
        for src, dst, w in g[currentNode]:
            distances[dst] = min(distances[dst], distances[src] + w)
            if distances[dst] == distances[src] + w:
                prevs[dst] = src
    
    return distances, prevs
            


#####################################################################

def genPath(prevs, currentNode):
    """
    This function will return the path from the initial node to the currentNode.
    """
    path = [currentNode]
    while prevs[currentNode] is not None:
        currentNode = prevs[currentNode]
        path.append(currentNode)
    return path[::-1]


g = [
    [(0, 1, 2)], 
    [(1, 2, 5), (1, 4, 3)],
    [(2, 5, 1)],
    [],
    [(4, 2, 1), (4, 3, 11), (4, 5, 6)],
    [(5, 3, 1)]
]

initial = 0
solution, prevs = dijkstra(g, initial)
print(solution, prevs)

for i in range(0, len(g)):
    print(genPath(prevs, i))