delucas
commented
3 years ago Está muy buena la explicación, sería el README de un proyecto, que tenga el código de Dijkstra. Pero habría que hacer el proyecto completo, basado en la estructura de Grafos
Closed facuegon481 closed 3 years ago
delucas
commented
3 years ago Está muy buena la explicación, sería el README de un proyecto, que tenga el código de Dijkstra. Pero habría que hacer el proyecto completo, basado en la estructura de Grafos
delucas
commented
3 years ago Referido en otro issue
Algoritmo de Dijkstra
El algoritmo de Dijkstra se utiliza para determinar el camino más corto, dado un vértice origen, hacia el resto de los vértices en un grafo que tienen pesos en cada arista.
El algoritmo se basa en ir explorando todos los caminos posibles desde el nodo de origen hacia los demás e ir actualizando los costos de una manera greedy. El algoritmo se detendrá cuando se encuentren todos los nodos en el conjunto solución. La formula a utilizar en este algoritmo será: d[v] = min (d[v], d[a] + c[a,v]) (mínimo entre la forma que tenemos de llegar al nodo y el costo que tengo de llegar al nodo pasando por ‘a’).
Para la representación de los costos mínimos a cada uno de los nodos se utilizará un vector de distancia de la misma forma que se utilizará un vector para la precedencia.
Dijkstra puede llegar a implementarse utilizando una matriz o una lista de adyacencias para representar los caminos entre los nodos. En el caso de utilizar una matriz vamos a tener una complejidad computacional de O(n2). En cambio utilizando una lista y con la ayuda de montículo mínimo la complejidad computacional quedaría O(A * log N) donde N es el numero de nodos y A de aristas.
Ejemplo
A continuación, se explicará el algoritmo implementando una lista y un montículo de mínima. Tomando el siguiente grafo, partiendo del nodo 5.
Se coloca 0 la posición 5 de los vectores de distancia y precedencia ya que es de donde se parte.
Iteración 1
Se procesa los adyacentes al nodo 5 y se calcula los valores de los mismos en el vector aplicando la fórmula de del mínimo costo. Los adyacentes al nodo 5 se agregan en el montículo (de 5 a 2 y 5 a 4). Se modifican la posición 2 y 4 de los vectores de precedencia y distancia con los valores correspondientes.
Iteración 2
Se procesa los adyacentes del nodo 4, ya que es el menor valor del montículo, y se agrega las aristas adyacentes al nodo 4 al montículo (de 4 a 3 y 4 a 2). Son modificados la posición 2 y 3 de los vectores de distancia y precedencia con los valores calculados. Se agrega al nodo 4 como conjunto solución.
Iteración 3
Se procesa los adyacentes del nodo 2, ya que es el menor dentro del montículo, y se agrega los mismos dentro del montículo (de 2 a 1). Se modificó la posición 1 de los vectores de distancia y presidencia con los valores calculados. Se agrega al nodo 2 como conjunto solución.
Iteración 4
Se procesa los adyacentes del nodo 3, ya que es el menor del montículo, y se agregan los mismos en el montículo (de 3 a 4). Ambos vectores quedan igual, ya que se calculó un valor mayor al que ya existía. Se agrega el nodo 3 al conjunto solución.
Iteración 5
Se intenta agarrar el menor dentro del montículo (de 3 a 4) pero esto no agrega ningún nodo nuevo al conjunto solución, entonces se saca del montículo y va por el siguiente (2 a 1). Se agrega los adyacentes del nodo 1 al montículo. Ambos vectores quedan igual, ya que se calculó un valor mayor al que ya existía. Se agrega el nodo 1 al conjunto solución.
Se obtuvo en el conjunto solución todos los nodos disponibles, entonces el algoritmo termina y deja en el vector distancia la distancia mínima desde 5 a todos los otros nodos, el vector precedencia refleja el camino correcto para obtener dicha distancia.