Grafos en Python - Teoría e Implementación - Algoritmo de Dijkstra

Los gráficos son una estructura de datos extremadamente versátil. ¡Más de lo que la mayoría de la gente cree! Los gráficos se pueden usar para modelar prácticamente cualquier cosa, dada su naturaleza de modo...

El algoritmo de Dijkstra está diseñado para encontrar los caminos más cortos entre nodos en un gráfico. Fue diseñado por un informático holandés, Edsger Wybe Dijkstra, en 1956, cuando sopesaba la ruta más corta de Róterdam a Groningen. Se publicó tres años después.

{.icon aria-hidden=“true”}

Nota: El algoritmo de Dijkstra ha experimentado cambios a lo largo de los años y existen varias versiones y variaciones. Originalmente, se usaba para calcular la ruta más corta entre dos nodos. Debido a la forma en que funciona, se adaptó para calcular la ruta más corta entre un nodo inicial y cualquier otro nodo en el gráfico. De esta manera, se puede usar para producir un árbol de ruta más corta que consta de la ruta más corta entre dos nodos, así como todos los demás nodos. Luego puede podar los árboles que no le interesen, obteniendo el camino más corto entre dos nodos, pero inevitablemente tendrá que calcular todo el árbol, lo cual es un inconveniente del algoritmo de Dijkstra que lo hace inadecuado. para gráficos grandes.
Nos centraremos en la última implementación de la lección.

En esta lección, echaremos un vistazo al algoritmo de Dijkstra, la intuición detrás de él y luego lo implementaremos en Python.

Algoritmo de Dijkstra - Teoría e intuición

El algoritmo de Dijkstra funciona en gráficos no dirigidos, conectados y ponderados.

Al principio, querremos crear un conjunto de vértices visitados, para realizar un seguimiento de todos los vértices a los que se les ha asignado su ruta más corta correcta. También necesitaremos establecer "costos" de todos los vértices en el gráfico (longitudes del camino actual más corto que conduce a él).

Todos los costos se establecerán en 'infinito' al principio, para asegurarnos de que cualquier otro costo con el que podamos compararlo sea menor que el inicial. La única excepción es el costo del primer vértice inicial: este vértice tendrá un costo de 0, porque no tiene una ruta hacia sí mismo, marcado como nodo s.

Luego, repetimos dos pasos principales hasta recorrer el grafo (siempre y cuando haya vértices sin el camino más corto asignado):

  • Elegimos un vértice con el costo actual más corto, lo visitamos y lo agregamos al conjunto de vértices visitados.
  • Actualizamos las costas de todos sus vértices adyacentes que aún no se visitan. Para cada borde entre n y m donde m no se visita - si cheapestPath(s, n) + cheapestPath(n,m) < cheapestPath(s,m), actualice el ruta más barata entre s y m para igualar cheapestPath(s,n) + cheapestPath(n,m).

Dado que esto puede ser un poco difícil de comprender, ¡visualicemos el proceso antes de implementarlo! Aquí hay un gráfico no dirigido, ponderado y conectado:

paso 1 de dijkstra

Digamos que Vertex 0 es nuestro punto de partida. Vamos a establecer los costos iniciales de los vértices en este gráfico a infinito, excepto el vértice inicial:

costo del vértice para llegar desde el vértice 0


0 0 1 información 2 inf 3 inf 4 inf 5 inf 6 inf 7 inf 8 inf

Elegimos el vértice con un costo mínimo, es decir, Vértice 0. Lo marcaremos como visitado y lo agregaremos a nuestro conjunto de vértices visitados. El nodo inicial siempre tendrá el costo más bajo, por lo que siempre será el primero en agregarse:

dijkstra paso 2

Luego, actualizaremos el costo de los vértices adyacentes (1 y 6). Dado que 0 + 4 < infinito y 0 + 7 < infinito, actualizamos los costos a estos vértices:

costo del vértice para llegar desde el vértice 0


0 0 1 4 2 inf 3 inf 4 inf 5 inf 6 7 7 inf 8 inf

Ahora visitamos el siguiente vértice de menor costo. El peso de 4 es menor que el de 7, por lo que pasamos al Vértice 1:

dijkstra paso 3

Al atravesarlo, lo marcamos como visitado y luego observamos y actualizamos los vértices adyacentes: 2, 6 y 7:

  • Como 4 + 9 < infinito, el nuevo costo del vértice 2 será 13
  • Como 4 + 11 > 7, el costo del vértice 6 seguirá siendo 7
  • Como 4 + 20 < infinito, el nuevo costo del vértice 7 será 24

Estos son nuestros nuevos costos:

costo del vértice para llegar desde el vértice 0


0 0 1 4 2 13 3 inf 4 inf 5 inf 6 7 7 24 8 inf

El próximo vértice que vamos a visitar es Vértice 6. Lo marcamos como visitado y actualizamos los costos de sus vértices adyacentes:

dijkstra paso 4

costo del vértice para llegar desde el vértice 0


0 0 1 4 2 13 3 inf 4 inf 5 inf 6 7 7 8 8 inf

El proceso continúa hasta Vertex 7:

dijkstra paso 5

costo del vértice para llegar desde el vértice 0


0 0 1 4 2 13 3 inf 4 9 5 inf 6 7 7 8 8 11

Y de nuevo, a Vértice 4:

dijkstra paso 6

costo del vértice para llegar desde el vértice 0


0 0 1 4 2 11 3 19 4 9 5 24 6 7 7 8 8 11

Y de nuevo, a Vértice 2:

dijkstra paso 7

El único vértice que vamos a considerar es Vértice 3. Como 11 + 6 < 19, el costo del vértice 3 se actualiza.

Luego, procedemos al Vértice 8:

dijkstra paso 8

Finalmente, estamos actualizando Vertex 5:

costo del vértice para llegar desde el vértice 0


0 0 1 4 2 11 3 17 4 9 5 24 6 7 7 8 8 11

Hemos actualizado los vértices en la estructura similar a un bucle al final, por lo que ahora solo tenemos que atravesarlo, primero a Vértice 3:

dijkstra paso 9

Y finalmente, al Vertex 5:

dijkstra paso 10

No hay más vértices no visitados que puedan necesitar una actualización. Nuestros costos finales representan las rutas más cortas desde el nodo 0 hasta todos los demás nodos del gráfico:

costo del vértice para llegar desde el vértice 0


0 0 1 4 2 11 3 17 4 9 5 24 6 7 7 8 8 11

Puede podar esta tabla y simplemente mantener la distancia entre *Nodo X* y *Nodo Y*, sin embargo, tendrá que ejecutar este cálculo de todos modos para que realmente no reduzca el costo computacional.

Implementar el algoritmo de Dijkstra en Python

Ahora que hemos repasado el proceso paso a paso, ¡veamos cómo podemos implementar el algoritmo de Dijkstra en Python! Para ordenar y realizar un seguimiento de los vértices que aún no hemos visitado, usaremos un PriorityQueue:

1
from queue import PriorityQueue

Ahora, implementaremos un constructor para una clase llamada Graph:

1
2
3
4
5
class Graph:
    def __init__(self, num_of_vertices):
        self.v = num_of_vertices
        self.edges = [[-1 for i in range(num_of_vertices)] for j in range(num_of_vertices)]
        self.visited = []

En este constructor parametrizado simple, proporcionamos el número de vértices en el gráfico como argumento e inicializamos tres campos:

  • v: Representa el número de vértices del gráfico.
  • aristas: Representa la lista de aristas en forma de matriz. Para los nodos u y v, self.edges[u][v] = peso del borde.
  • visited: Un conjunto que contendrá los vértices visitados.

Ahora, definamos una función que agregará un borde a un gráfico:

1
2
3
    def add_edge(self, u, v, weight):
        self.edges[u][v] = weight
        self.edges[v][u] = weight

Con nuestra definición de gráfico fuera del camino, definamos el algoritmo de Dijkstra:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def dijkstra(graph, start_vertex):
    D = {v:float('inf') for v in range(graph.v)}
    D[start_vertex] = 0

    pq = PriorityQueue()
    pq.put((0, start_vertex))

    while not pq.empty():
        (dist, current_vertex) = pq.get()
        graph.visited.append(current_vertex)

        for neighbor in range(graph.v):
            if graph.edges[current_vertex][neighbor] != -1:
                distance = graph.edges[current_vertex][neighbor]
                if neighbor not in graph.visited:
                    old_cost = D[neighbor]
                    new_cost = D[current_vertex] + distance
                    if new_cost < old_cost:
                        pq.put((new_cost, neighbor))
                        D[neighbor] = new_cost
    return D

En este código, primero creamos una lista D del tamaño v. La lista completa se inicializa hasta el infinito. Esta será una lista en la que mantendremos las rutas más cortas desde start_vertex a todos los demás nodos.

Establecemos el valor del vértice de inicio en 0, ya que esa es su distancia de sí mismo. Luego, inicializamos una cola de prioridad, que usaremos para ordenar rápidamente los vértices de menor a mayor distancia. Ponemos el vértice de inicio en la cola de prioridad. Ahora, para cada vértice en la cola de prioridad, primero los marcaremos como visitados y luego iteraremos a través de sus vecinos.

Si el vecino no es visitado, compararemos su costo antiguo y su costo nuevo. El costo antiguo es el valor actual del camino más corto desde el vértice inicial al vecino, mientras que el costo nuevo es el valor de la suma del camino más corto desde el vértice inicial al vértice actual y la distancia entre el vértice actual y el Vecino. Si el costo nuevo es más bajo que el costo anterior, colocamos al vecino y su costo en la cola de prioridad y actualizamos la lista donde mantenemos las rutas más cortas en consecuencia.

Finalmente, después de visitar todos los vértices y la cola de prioridad está vacía, devolvemos la lista D.

Inicialicemos un gráfico que hemos usado antes para validar nuestros pasos manuales y probar el algoritmo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
g = Graph(9)
g.add_edge(0, 1, 4)
g.add_edge(0, 6, 7)
g.add_edge(1, 6, 11)
g.add_edge(1, 7, 20)
g.add_edge(1, 2, 9)
g.add_edge(2, 3, 6)
g.add_edge(2, 4, 2)
g.add_edge(3, 4, 10)
g.add_edge(3, 5, 5)
g.add_edge(4, 5, 15)
g.add_edge(4, 7, 1)
g.add_edge(4, 8, 5)
g.add_edge(5, 8, 12)
g.add_edge(6, 7, 1)
g.add_edge(7, 8, 3) 

Ahora, simplemente llamaremos a la función que ejecuta el algoritmo de Dijkstra en este gráfico e imprimiremos los resultados:

1
2
3
4
D = dijkstra(g, 0)

print(D)
# {0: 0, 1: 4, 2: 11, 3: 17, 4: 9, 5: 22, 6: 7, 7: 8, 8: 11}

O bien, podríamos formatearlo un poco mejor:

1
2
for vertex in range(len(D)):
    print("Distance from vertex 0 to vertex", vertex, "is", D[vertex])

Una vez compilamos el programa, obtendremos esta salida:

1
2
3
4
5
6
7
8
9
Distance from vertex 0 to vertex 0 is 0
Distance from vertex 0 to vertex 1 is 4
Distance from vertex 0 to vertex 2 is 11
Distance from vertex 0 to vertex 3 is 17
Distance from vertex 0 to vertex 4 is 9
Distance from vertex 0 to vertex 5 is 22
Distance from vertex 0 to vertex 6 is 7
Distance from vertex 0 to vertex 7 is 8
Distance from vertex 0 to vertex 8 is 11

La distancia entre el nodo inicial y cada uno de los demás nodos en el árbol se calcula y genera.

Complejidad del tiempo {#complejidad del tiempo}

En este algoritmo, pasamos cada arista una vez, lo que resulta en una complejidad de tiempo de O(|E|), donde |E| representa el número de aristas.

También visitamos cada nodo una vez, lo que da como resultado una complejidad temporal de O(|V|), donde |V| representa el número de vértices. Cada vértice se colocará en una cola de prioridad, donde la búsqueda del siguiente vértice más cercano se realizará en un tiempo constante de ‘O (1)’. Sin embargo, usamos el tiempo O(Vlog|V|) para ordenar los vértices en esta cola de prioridad.

Esto da como resultado que la complejidad de tiempo de este algoritmo sea O(|E|+|V|log|V|). )`.

Licensed under CC BY-NC-SA 4.0