Dijksta

A
L
G
O
R
I
T
M
O
D
E
D
I
J
K
S
T
R
A

## ¿QUE ES EL ALGORITMO DE DIJKSTRA

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de los vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.

## DESCRIPCIÓN

El algoritmo de dijkstra determina la ruta más corta desde un nodo origen hacia los demás nodos para ello es requerido como entrada un grafo cuyas aristas posean pesos. Algunas consideraciones:
- Si los pesos de mis aristas son de valor 1, entonces bastará con usar el algoritmo de BFS.
- Si los pesos de mis aristas son negativos no puedo usar el algoritmo de dijsktra, para pesos negativos tenemos otro algoritmo llamado Algoritmo de Bellmand-Ford.

  ## COMO TRABAJA EL ALGORITMO DE DIJKSTRA

  1)Primero marcamos todos los vértices como no utilizados.
  2) El algoritmo parte de un vértice origen que será ingresado, a partir de ese vértices evaluaremos sus adyacentes, como dijkstra usa una técnica greedy (La técnica greedy utiliza el principio de que para que un camino sea óptimo), todos los caminos que contiene también deben ser óptimos.
  3) Entre todos los vértices adyacentes, buscamos el que esté más cerca de nuestro punto origen, lo tomamos como punto intermedio y vemos si podemos llegar más rápido a través de este vértice a los demás.
  4) Después escogemos al siguiente más cercano (con las distancias ya actualizadas) y repetimos el proceso. Esto lo hacemos hasta que el vértice no utilizado más cercano sea nuestro destino. Al proceso de actualizar las distancias tomando como punto intermedio al nuevo vértice se le conoce como relajación (relaxation).

  ## EJEMPLO

  Encontrar la ruta mas corta del nodo 1 al 6 del Siguiente Grafo:

  ### PASO Nº1:

- El primer valor acumulado es 0 porque no se lleva nada hasta el momento.
- El nodo de procedencia no existe hasta el momento entonces es - .
- La iteración es 0 porque todavía no existen operaciones.

  ### PASO Nº2

- Avanzar al siguiente nodo (En este caso seria el nodo 2).
- Comparar nodos y marcar como definitivo el que tenga el numero menor en numero acumulado.

  ### PASO Nº3

- Para obtener el valor acumualdo del nodo 4, sumaremos el valor acumulado del nodo definitivo con el valor que va hacia el nodo 4, de esta manera quedaria lo siguiente 1+3 = 1.
- Comparar nodo 2, 4, 5 y marcar el nodo definitivo.

  ### PASO Nº4

- Eliminar y sacar nuevos valores de acumulacion para el nodo 4, como ya se habia mencionado anteriormente, si viene del nodo 2 sumamos el valor acumulado de ese nodo mas el nuevo valor, 2+1 = 3.

  ### PASO Nº5

- Comparar nodos 4 y 5 y marcar nodo definitivo.

  ### PASO Nº6

- Observemos que el nodo 5 y 6 tienen el mismo numero de valor acumulado(5), por lo tanto se marca como nodo definitivo el nodo que este mas cerca de la ruta, en este caso es el nodo numero 5.

  ### PASO Nº7

- Finalmente podemos marcar nuestra ruta y distancia, ya que, no hay mas operaciones que se puedan realizar.
  Por lo tanto:
  RUTA: La obtenemos con los nodos de procedencia de atras hacia adelante, nuestra ruta es la siguiente:
  RUTA 1-6 = 1, 2, 4, 6.
  DISTANCIA Ultimo valor acumulado en este caso:
  DISTANCIA = 5

  ## VIDEO COMPLEMENTARIO

  #### IO Tutoriales - 02 Algoritmo de DIJKSTRA

  ## REFERENCIAS ELECTRONICAS

- https://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra
- https://www.ecured.cu/Algoritmo_de_Dijkstra
- https://jariasf.wordpress.com/2012/03/19/camino-mas-corto-algoritmo-de-dijkstra/