# **Método de Dijkstra y algunas aplicaciones**

## Objetivos:
- Leer sobre el método de Dijkstra y la teoría de grafos.
- Comprender el pseudo-código del método de Dijkstra.
- Implementar el algoritmo en Julia.

## Alcance:

## Teórico:
## ***MÉTODO DE DIJKSTRA***
El algoritmo de Dijkstra es un algoritmo utilizado para encontrar el camino más corto en un grafo ponderado, es decir, un grafo en el que cada arista tiene asociado un valor numérico llamado peso o costo. Fue desarrollado por el científico de la computación Edsger Dijkstra en 1956.

**Algoritmo del Método de Dijkstra**

Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial. Un vector D de tamaño N guardará al final del algoritmo las distancias desde x hasta el resto de los nodos.
1. Inicializar todas las distancias en D con un valor infinito relativo, ya que son desconocidas al principio, exceptuando la de x, que se debe colocar en 0.
2. Sea a=x (Se toma a como nodo actual).
3. Se recorren todos los nodos adyacentes de a, excepto los nodos marcados. Se les llamará nodos no marcados v_i.
4. Para el nodo actual, se calcula la distancia tentativa desde dicho nodo hasta sus vecinos con la siguiente fórmula dt(V_i)=D_a+d(a, v_i). Es decir, la distancia tentativa del nodo "v_i" es la distancia que actuamente tiene el nodo en el vector D más la distancia desde dicho nodo "a" (el actual) hasta el nodo v_i. Si la distancia tentativa es menor que la distancia almacenada en el vector, entonces se actualiza el vector con esta distancia tentativa. Es decir, si dt(V_i)< D_vi → D_vi=dt(V_i).
5. Se marca como completo el nodo a.
6. Se toma como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y se regresa al paso 3, mientras existan nodos no marcados.

Una vez terminado el algoritmo, D estará completamente lleno.

using DataStructures
- Inicializar distancias con infinito para todos los nodos, excepto el nodo de inicio
- Crear una cola de prioridad para almacenar los nodos no visitados
- Obtener el nodo con la distancia mínima
- Recorrer los nodos adyacentes al nodo actual
- Calcular la nueva distancia hasta el nodo adyacente
- Actualizar la distancia si es menor a la distancia actual almacenada
- Actualizar la cola de prioridad con la nueva distancia

POSIBLE CÓDIGO - Me sale un error cuando quiero usar la cola de prioridad (PriorityQueue) del paquete DataStructures

using DataStructures # Necesario para utilizar la cola de prioridad

## Bibliografía:

- https://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra

## Idea (grafos)

Para representar grafos, una manera comun es utilizar listas de adjacencia.

struct Grafo # o GrafoDirigido
    nodos::Vector{Int64}
    fadj::Vector{Vector{Int64}}
    pesos::Matrix{Float64}
end

Por ejemplo, `1 -> 2`, `1 -> 3`, `2 -> 3`, `3 -> 3`.

nodos = [1, 2, 3]
fadj = [[2, 3], [3], [3]]

La "f" en fadj viene de forward que en ingles significa para adelante.

Los pesos los puedo representar como una matriz de $n x n$. Para el ejemplo anterior,

pesos = [0 1. 2.;
         0 0 3.;
         0 0 1.]

Grafo de ejemplo:

Grafo(nodos, fadj, pesos)

Por ejemplo, para el algoritmo de Dijkstra me va a interesar implementar una funcion que se llame "sucesores" que dado un nodo, me da los nodos a los cuales esta conectados.

function sucesores(G::Grafo, u::Int64)
    # Chequear que u es un nodo valido.
    if u ∉ nodos
        throw(ArgumentError("El nodo no es valido."))
    end
    
    G.fadj[u]
end