Algoritmo de Dijsktra

El algoritmo de Dijkstra (algoritmo de caminos mínimos), es un algoritmo para la distancia más corta de un punto a cualquier otro. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del nodo origen y que llevan a todos los demás nodos; cuando se obtiene el camino más corto desde el nodo origen, al resto de nodos que componen el grafo, el algoritmo se detiene.

Explicación del Algoritmo:

Supongamos que tenemos los siguientes nodos con sus respectivas distancias entre ellos.

Para este ejemplo, vamos a calcular la distancia más corta del Nodo 4 a cualquier otro.

Primero calcularemos las etiquetas correspondientes a cada nodo. Una etiqueta consta de dos partes: la distancia a cumulada y el nodo de procedencia.

[acumulado, procedencia]

Donde:

Distancia = distancia entre el nodo base y el nodo actual.
Distancia acumulada = acumulado del nodo base + distancia
Nodo de procedencia = nodo base

Conforme vallamos calculando las etiquetas iremos marcando los nodos para que no se nos forme un ciclo infinito.

Como en nuestro caso el Nodo 4 es nuestro punto de inicio, por ahora será nuestro Nodo base, lo marcamos y como no tiene distancia acumulada y nodo de procedencia su etiqueta será: [0,0].

Paso 1:

Ahora buscaremos que nodos están conectados al Nodo 4, los cuales son: 1, 3, 6 y 7.

Calculemos la etiqueta de cada uno de los nodos conectados al Nodo base:

Etiqueta del Nodo 1:

Nodo actual = Nodo 1
Distancia = Distancia del Nodo base al Nodo actual = 3
Distancia acumulada = Acumulado del Nodo base + Distancia = 0+3 = 3
Procedencia = Nodo 4

La etiqueta del Nodo 1 quedaría: [3, Nodo 4]

Etiqueta del Nodo 3:

Nodo actual = Nodo 3
Distancia = Distancia del Nodo base al Nodo actual = 2
Distancia acumulada =Acumulado del Nodo base + Distancia =0+2 = 2
Procedencia = Nodo 4

La etiqueta del Nodo 3 quedaría: [2, Nodo 4]

Etiqueta del Nodo 6:

Nodo actual = Nodo 6
Distancia = Distancia del Nodo base al Nodo actual = 1
Distancia acumulada =Acumulado del Nodo base + Distancia =0+1 = 1
Procedencia = Nodo 4

La etiqueta del Nodo 6 quedaría: [1, Nodo 4]

Etiqueta del Nodo 7:

Nodo actual = Nodo 7
Distancia = Distancia del Nodo base al Nodo actual = 3
Distancia acumulada =Acumulado del Nodo base + Distancia =0+3 = 3
Procedencia = Nodo 4

La etiqueta del Nodo 7 quedaría: [3, Nodo 4]

Una vez calculadas las etiquetas de los nodos, buscaremos el Nodo que tenga la etiqueta con menor distancia acumulada y que no esté marcado, como vemos es el Nodo 6.

Ahora el Nodo 6 pasará a ser nuestro Nodo base y lo marcamos.

Paso 2:

Buscamos los Nodos conectados al Nodo 6 y que NO estén marcados: 3, 5 y 7.

Calculemos la etiqueta de cada uno de los nodos conectados al Nodo base:

Etiqueta del Nodo 3:

Nodo actual = Nodo 3
Distancia = Distancia del Nodo base al Nodo actual = 2
Distancia acumulada = Acumulado del Nodo base + Distancia = 1+2 = 3
Procedencia = Nodo 6

Como la distancia acumulada es mayor que la distancia acumulada que tiene establecida en su etiqueta el Nodo 3, entonces la etiqueta actual no se asigna, ya que solo buscamos etiquetas menores o iguales a la ya establecida.

Por tanto la etiqueta del Nodo 3 quedaría: [2, Nodo 4]

Etiqueta del Nodo 7:

Nodo actual = Nodo 7
Distancia = Distancia del Nodo base al Nodo actual = 2
Distancia acumulada = Acumulado del Nodo base + Distancia = 1+2 = 3
Procedencia = Nodo 6

En este caso la distancia acumulada es igual que la distancia acumulada que tiene establecida en su etiqueta el Nodo 7, entonces la etiqueta actual se añade, ya que solo buscamos etiquetas menores o iguales a la ya establecida.

Las etiquetas del Nodo 7 quedarían: [3, Nodo 4], [3, Nodo 6]

Etiqueta del Nodo 5:

Nodo actual = Nodo 5
Distancia = Distancia del Nodo base al Nodo actual = 3
Distancia acumulada = Acumulado del Nodo base + Distancia = 1+3 = 4
Procedencia = Nodo 6

La etiqueta del Nodo 5 quedaría: [4, Nodo 6]

Una vez calculadas las etiquetas de los nodos, buscaremos el Nodo que tenga la etiqueta con menor distancia acumulada y que no esté marcado, el cual ahora es el Nodo 3.

Ahora el Nodo 3 pasará a ser nuestro Nodo base y lo marcamos.

Paso 3:

Buscamos los Nodos conectados al Nodo 3 y que NO estén marcados: 2 y 5.

Calculemos la etiqueta de cada uno de los nodos conectados al Nodo base:

Etiqueta del Nodo 2:

Nodo actual = Nodo 2
Distancia = Distancia del Nodo base al Nodo actual = 1
Distancia acumulada = Acumulado del Nodo base + Distancia = 2+1 = 3
Procedencia = Nodo 3

La etiqueta del Nodo 2 quedaría: [3, Nodo 3]

Etiqueta del Nodo 5:

Nodo actual = Nodo 5
Distancia = Distancia del Nodo base al Nodo actual = 3
Distancia acumulada = Acumulado del Nodo base + Distancia = 2+3 = 5
Procedencia = Nodo 3

Como la distancia acumulada es mayor que la distancia acumulada que tiene establecida en su etiqueta el Nodo 5, entonces la etiqueta actual no se asigna, ya que solo buscamos etiquetas menores o iguales a la ya establecida.

La etiqueta del Nodo 5 quedaría: [4, Nodo 6]

Ya encontradas las etiquetas de los nodos, buscaremos el Nodo que tenga la etiqueta con menor acumulado y que no esté marcado. Ahora, si nos damos cuenta los Nodos 1, 2 y 7 tienen igual distancia acumulada, cuando esto ocurre optamos por tomar cualquiera de ellos aleatoriamente como nuestro Nodo base, en este caso tomaremos el Nodo 7.

Ahora el Nodo 7 pasará a ser nuestro Nodo base y lo marcamos.

Paso 4:

Buscamos los Nodos conectados al Nodo 7 y que NO estén marcados.

En este caso no tiene nodos conectados que no estén marcados.

Buscamos el Nodo que tenga la etiqueta con menor acumulado y que no esté marcado, como vemos ahora los Nodos 1 y 2 tienen igual distancia acumulada, tomamos cualquiera de ellos aleatoriamente, en este caso tomaremos el Nodo 2.

Ahora el Nodo 2 pasará a ser nuestro Nodo base y lo marcamos.

Paso 5:

Buscaremos los Nodos conectados al Nodo 2 y que NO estén marcados: 1 y 5.

Calculemos la etiqueta de cada uno de los nodos conectados al Nodo base:

Etiqueta del Nodo 5:

Nodo actual = Nodo 5
Distancia = Distancia del Nodo base al Nodo actual = 2
Distancia acumulada = Acumulado del Nodo base + Distancia = 3+2 = 5
Procedencia = Nodo 2

Ahora, como la distancia acumulada es mayor que la distancia acumulada que tiene establecida en su etiqueta el Nodo 5, entonces la etiqueta actual no se asigna, ya que solo buscamos etiquetas menores o iguales a la ya establecida.

La etiqueta del Nodo 5 quedaría: [4, Nodo 6]

Etiqueta del Nodo 1:

Nodo actual = Nodo 1
Distancia = Distancia del Nodo base al Nodo actual = 3
Distancia acumulada = Acumulado del Nodo base + Distancia = 3+3 = 3
Procedencia = Nodo 2

Como la distancia acumulada es mayor que la distancia acumulada que tiene establecida en su etiqueta el Nodo 1, entonces la etiqueta actual no se asigna, ya que solo buscamos etiquetas menores o iguales a la ya establecida.

La etiqueta del Nodo 1 quedaría: [3, Nodo 4]

Ahora buscaremos el Nodo que tenga la etiqueta con menor acumulado y que no esté marcado, ahora es el Nodo 1.

Ahora el Nodo 1 pasará a ser nuestro Nodo base y lo marcamos.

Paso 6:

Ahora buscaremos los Nodos conectados al Nodo 1 y que NO estén marcados.

Como vemos no tiene nodos conectados que no estén marcados.

Buscamos el Nodo que tenga la etiqueta con menor acumulado y que no esté marcado, como vemos el único que queda libre es el Nodo 5.

Ahora el Nodo 5 pasará a ser nuestro Nodo base y lo marcamos.

Paso 7:

Buscamos los Nodos conectados al Nodo 5 y que NO estén marcados.

Observamos que no tiene nodos conectados que no estén marcados.

Ahora buscaremos el Nodo que tenga la etiqueta con menor acumulado y que no esté marcado.

Si nos damos cuenta ya no existen nodos sin marcar, por lo tanto hemos terminado de calcular las etiquetas a cada Nodo.

Las etiquetas deben ser las siguientes:

Nodo 1: [3,4]
Nodo 2: [3,3]
Nodo 3: [2,4]
Nodo 4: [0,0]
Nodo 5: [4,6]
Nodo 6: [1,4]
Nodo 7: [3,4], [3,6]

Ejemplos.

Ahora, si nos pidieran calcular la distancia más corta del Nodo 4 a cualquier otro (recordemos que debe ser el Nodo 4 nuestro punto de inicio, ya que a partir de él calculamos las etiquetas), lo haremos de la siguiente manera.

Ejemplo: calcular la ruta más corta del Nodo 4 al Nodo 5.

Primero nos ubicamos en el Nodo 5 y de su etiqueta ([4,6]) extraemos su procedencia y vemos que es el Nodo 6.

Ahora nos ubicamos en el Nodo 6 y de su etiqueta ([1,4]) extraemos su procedencia y vemos que es el Nodo 4.

Como el Nodo 4 es nuestro punto de inicio, podemos decir que la ruta más corta para ir del Nodo 4 al Nodo 5, es pasando por los nodos Nodo 4, Nodo 6 y Nodo 5.

Ejemplo: calcular la ruta más corta del Nodo 4 al Nodo 7.

Primero nos ubicamos en el Nodo 7, como vemos que tiene dos etiquetas primero de su etiqueta ([3,4]) extraemos su procedencia y vemos que es el Nodo 4.

Como el Nodo 4 es nuestro punto de inicio, podemos decir que la ruta más corta para ir del Nodo 4 al Nodo 7, es pasando por los nodos Nodo 4 y Nodo 7.

Ahora, de su etiqueta ([3,6]) extraemos su procedencia y vemos que es el Nodo 6.

Nos ubicamos en el Nodo 6 y de su etiqueta ([1,4]) extraemos su procedencia y vemos que es el Nodo 4.

Como el Nodo 4 es nuestro punto de inicio, podemos decir que la ruta más corta para ir del Nodo 4 al Nodo 7, es pasando por los nodos Nodo 4, Nodo 6 y Nodo 7.

Entonces podemos decir que la ruta más corta para ir del Nodo 4 al Nodo 7, es pasando por los nodos Nodo 4 y Nodo 7 ó por los nodos Nodo 4, Nodo 6 y Nodo 7.

Así, si quisiéramos calcular la ruta más corta, tomando como inicio cualquier otro nodo, primero tendríamos que obtener las etiquetas y de allí los nodos por los cual se forma la ruta.

Espero sea de su ayuda!

Programa hecho en Ruby para calcular la distancia más corta de una estación a otra del metro del D.F.

Explicación de un programa hecho en Ruby para calcular la distancia más corta de una estación a otra del metro del D.F.

El programa cuenta con cuatro clases:

- Label
- Node
- Route
- Dijkstra

La clase Label:

La clase Label (etiqueta) cuenta con dos atributos (acumulado y procedencia) con sus respectivos métodos geters y seters, además de un constructor donde inicializamos los atributos.

Código:

class Label
 	def initialize(accumulated, provenance)
		@accumulated = accumulated
		@provenance = provenance
	end
  	def get_accumulated
    		return @accumulated
  	end
  	def get_provenance
    		return @provenance
  	end
end

La clase Node:

La clase Node (nodo) cuenta con cinco atributos con sus respectivos métodos geters y seters, además de un constructor donde inicializamos los atributos:

Id: que será con el cual vamos a identificar al nodo.

Nombre (name): que será el nombre del nodo.

Eiquetas (labels): que serán las etiquetas que contenga el nodo, las cuales serán objetos de la clase Label.

Marcado (marked): nos ayudara para ir verificando si un nodo está o no marcado.

Código:

require "label.rb"
class Node
  	def initialize(id, name, accumulated, provenance, marked)
		@id = id
		@name = name
		@labels = []
		lab = Label.new(accumulated, provenance)
		@labels << lab
		@marked = marked
	end
	def set_id(id)
		@id = id
	end
	def set_name(name)
		@name = name
	end
  	def get_name
		return @name
	end
	def get_id
		return @id
	end
	def set_label(accumulated, provenance)
		@labels = []
		lab = Label.new(accumulated, provenance)
		@labels << lab
	end
	def get_accumulated
		return @labels[0].get_accumulated
	end
	def get_provenance
		return @labels[0].get_provenance
	end
 	def get_labels
    		return @labels
  	end
	def set_marked(mark)
		@marked = mark
	end
	def get_marked
		return @marked
	end
	def clear
    		@labels.clear
    		@labels << Label.new(0,0)
        	@marked = false
	end
end

La clase Route:

La clase Route (ruta) cuenta con tres atributos con sus respectivos métodos geters y seters, además de un constructor donde inicializamos los atributos:

Nodo inicio (begin_node): almacena el id de algún nodo.

Nodo fin (end_node): almacena el id de algún nodo.

Distancia (distance): distancia entre el begin_node y el end_node.

Esta clase se encarga de almacenar la distancia entre un nodo y otro con conexión directa (nodo inicio, nodo fin, distancia).

Código:

class Route
  	def initialize(begin_node, end_node, distance)
		@begin_node = begin_node
		@end_node = end_node
		@distance = distance
	end
	def set_begin_node(node)
		@begin_node = node
	end
	def set_end_node(node)
		@end_node = node
	end
	def set_distance(distance)
		@distance = distance
	end
	def get_begin_node
		return @begin_node
	end
	def get_end_node
		return @end_node
	end
	def get_distance
		return @distance
	end
end

La clase Dijkstra:

En esta clase es donde desarrollaremos el Algoritmo de Dijkstra.

Ahora, para este ejemplo las distancias de una estación a otra es 1, estas están cargadas en un archivo de texto en forma de matriz más o menos de la siguiente manera:

La clase cuenta con los siguientes atributos:

Matriz (matriz): carga la matriz almacenada en el archivo de texto.

Nodos (nodes): arreglo nodos creados cada una de la clase nodo, estos representan cada una de las estaciones del metro cardadas en la matriz.

Rutas (routes): arreglo de objetos creados de la clase Route que almacena las distancias entre una estación y otra.

Inicio (begin): es el nodo que tomaremos como punto de inicio.

Fin (end): es el nodo que tomaremos como punto final.

También cuenta con los siguiente métodos:

Genera matriz (generate_matrix): este se encarga de cargar la matriz almacenada en el archivo de texto y almacenarla en la variable matriz.

Carga lista (load_list): regresa un arreglo con los nodos (estaciones) almacenadas en la matriz.

Carga rutas (load_routes): regresa un arreglo con las distancias entre cada estación almacenadas en la matriz.

Ruta de inicio (begin_path): establece el punto de inicio.

Ruta final (end_path): establece el punto final.

Etiqueta menor (lower_label): busca la etiqueta con menor distancia acumulada.

Genera etiquetas (generate_labels): genera las etiquetas para cada nodo.

Nodos de la ruta corta (nodes_short_path): extrae los nodos que forma la ruta más corta.

Código:

require "node.rb"
require "route.rb"
class Dijkstra
	def generate_matrix(file)
		$matriz = []
		for i in 0...148
			$matriz << Array.new
		end
		l = $matriz.length-1
		if File.exists?(file)
			f = File.open(file)
			i = 0
			f.each do |linea|
				0.upto(l) do |j|
					$matriz[i] << linea.split(",")[j]
				end
				i += 1
			end
			f.close
		end
	end
	def load_list(file)
		generate_matrix(file)
		l = $matriz.length
		@nodes = []
		for i in 1...l
			node = Node.new(i-1,$matriz[0][i],0,0,false)
			@nodes << node
		end
		load_routes()
		return @nodes
	end
	def load_routes
		l = $matriz.length
		@routes = []
		for i in 1...l
			for j in 1...l
				if $matriz[i][j] != "0" then
					route=Route.new(i-1,j-1,$matriz[i][j].to_i)
					@routes << route
                                 end
                         end
                 end
                 return @routes
          end
          def node_search(name)
                 @nodes.each do |node|
                         return node if name == node.get_name
                 end
          end
          def begin_path(node)
                 @begin = node_search(node)
          end
          def end_path(node)
                 @end = node_search(node)
          end
          def lower_label
                  minor = 0
                  cond = false
                  m = -1
                  @nodes.each do |node|
                         if node.get_accumulated > 0 and !node.get_marked then
				if cond == false then
					minor = node.get_accumulated
					cond = true
					m = node.get_id
				end
                                if node.get_accumulated < minor and !node.get_marked then
					minor = node.get_accumulated
					m = node.get_id
				end
			end
		end
		if m != -1 then
			return @nodes[m]
		else
			return nil
		end
	end
	def generate_labels(nodebase)
		if nodebase then
			@nodes[nodebase.get_id].set_marked(true)
			@routes.each do |route|
				begin_node = route.get_begin_node
				end_node = route.get_end_node
				distance = route.get_distance
				if begin_node == nodebase.get_id and !@nodes[end_node].get_marked then
					if @nodes[end_node].get_accumulated == 0 or ((distance+nodebase.get_accumulated) < @nodes[end_node].get_accumulated) then
						@nodes[end_node].set_label(distance+nodebase.get_accumulated,nodebase.get_id)
					end
				end
			end
			generate_labels(lower_label())
		end
	end
	def short_path
	    clear
	    generate_labels(@begin)
	    routes = nodes_short_path(@end.get_id, @begin.get_id)
	    routes = routes.flatten
	    routes = routes.reverse
	    return routes
	end
	def nodes_short_path(node, nodebase)
		short_path_nodes = []
		@nodes[node].get_labels.each do |lab|
			if nodebase == lab.get_provenance then
				short_path_nodes << @nodes[node]
			else
				short_path_nodes << @nodes[node] << nodes_short_path(lab.get_provenance, nodebase)
			end
		end
		return short_path_nodes
	end
	def clear
	    @nodes.each do |node|
			node.clear
	    end
	end
end

¿Cómo funciona?

El programa cuenta con un archivo llamado index.rb, que es donde ejecutaremos nuestro programa.

Primero creamos un objeto de la clase Dijkstra.

@d=Dijkstra.new

Cargamos la lista de nodos de nuestro archivo, el cual llamamos ‘metro.txt’

nodes=@d.load_list('metro.txt')

Establecemos nuestro punto de inicio.

@d.begin_path('Potrero')

Establecemos nuestro punto final.

@d.end_path('Sevilla')

Ahora, el método short_path que nos regresa los nodos que forma la ruta corta, invoca al método generate_labels al cual le pasamos como parámetro nuestro punto de inicio, calcula las etiquetas de los nodos conectados al nodo pasado como parámetro, y este se hace recursivo invocándose así mismo, pasándose como parámetro la etiqueta menor, obtenida con el método lower_label.

Una vez calculadas las etiquetas se invoca al método nodes_short_path que extrae los nodos en forma de matriz y en orden contrario, por eso se ocupan los métodos flatten y reverse.

routes=@d.short_path

Imprimimos los nodos que forman la ruta.

routes.each do |r|
	puts r.get_name
end

Listo!!..

Programa

Pueden descagar el programa completo desde aquí:

dijkstra_rb

Espero sea de gran ayuda, no duden en comentar.. Saludos!