Algoritmo de Dijkstra en Python

El algoritmo de Dijkstra se puede definir como un algoritmo codicioso que se puede utilizar para encontrar la distancia más corta posible desde un vértice de origen a cualquier otro vértice posible que exista en un gráfico ponderado, siempre que el vértice sea accesible desde el vértice de origen.

Este tutorial analiza cómo implementar el algoritmo de Dijkstra para encontrar la ruta más corta en Python.

Como se mencionó anteriormente, el algoritmo de Dijkstra es codicioso. Un algoritmo codicioso se puede definir como un paradigma algorítmico que se enfoca en construir una solución pieza por pieza para el problema dado, eligiendo entonces la opción más beneficiosa.

El funcionamiento del algoritmo de Dijkstra es el siguiente.

• Dados un par de vértices no visitados, seleccione el vértice con la menor distancia desde la fuente y visítelo.
• A continuación, se actualiza la distancia de cada vecino. Lo mismo se hace para el vértice visitado, que tiene una distancia actual mayor que la suma y el peso del borde dado entre ellos.
• Los pasos 1 y 2 deben repetirse hasta que no queden vértices no visitados.

El algoritmo de Dijkstra se parece al algoritmo de árbol de expansión mínimo de Prim, otro algoritmo codicioso, ya que ambos necesitan la generación de un SPT (árbol de ruta más corta), tomando la fuente como la raíz del árbol.

El siguiente código utiliza el algoritmo de Dijkstra para encontrar la ruta más corta en Python.

import sys


class Graph:
    def __init__(self, vertx):
        self.V = vertx
        self.graph = [[0 for column in range(vertx)] for row in range(vertx)]

    def pSol(self, dist):
        print("Distance of vertex from source")
        for node in range(self.V):
            print(node, "t", dist[node])

    def minDistance(self, dist, sptSet):

        min = sys.maxsize

        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v

        return min_index

    def dijk(self, source):

        dist = [sys.maxsize] * self.V
        dist[source] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):

            u = self.minDistance(dist, sptSet)

            sptSet[u] = True

            for v in range(self.V):
                if (
                    self.graph[u][v] > 0
                    and sptSet[v] == False
                    and dist[v] > dist[u] + self.graph[u][v]
                ):
                    dist[v] = dist[u] + self.graph[u][v]

        self.pSol(dist)


f = Graph(9)
f.graph = [
    [0, 4, 0, 0, 0, 0, 0, 8, 0],
    [4, 0, 8, 0, 0, 0, 0, 11, 0],
    [0, 8, 0, 7, 0, 4, 0, 0, 2],
    [0, 0, 7, 0, 9, 14, 0, 0, 0],
    [0, 0, 0, 9, 0, 10, 0, 0, 0],
    [0, 0, 4, 14, 10, 0, 2, 0, 0],
    [0, 0, 0, 0, 0, 2, 0, 1, 6],
    [8, 11, 0, 0, 0, 0, 1, 0, 7],
    [0, 0, 2, 0, 0, 0, 6, 7, 0],
]

f.dijk(0)

El código anterior proporciona el siguiente Resultado:

Distance of vertex from source
0 t 0
1 t 4
2 t 12
3 t 19
4 t 21
5 t 11
6 t 9
7 t 8
8 t 14

El algoritmo de Dijkstra es muy similar al algoritmo de búsqueda en profundidad, aunque ambos algoritmos no existen precisamente para el mismo propósito.

La única diferencia significativa entre Depth First Search y el algoritmo de Dijkstra es que el primero funciona más lento que el segundo, ya que el algoritmo Depth First Search (DFS) utiliza la técnica de pila. Por otro lado, el algoritmo de Dijkstra hace uso de la técnica de pila comparativamente más lenta.