# TDA | Practica 5 ejercicio 2
## Consigna
- Diseñar un algoritmo eficiente que, dado un digrafo $G$ con pesos no negativos, dos vértices $s$ y $t$ y una cota $c$, determine una arista de peso máximo de entre aquellas que se encuentran en algún recorrido de $s$ a $t$ cuyo peso (del recorrido, no de la arista) sea a lo sumo $c$. Demostrar que el} algoritmo propuesto es correcto.
## Resolución
- Idea: Dijkstra
- Agregar una estructura adicional (diccionario por ej) para almacenar la arista de peso máximo.
- Modificación de la cota $c$:
- cuando exploras las aristas desde un vertice actual $u$, a sus vecinos adyacentes $v$.
- $u \to v$ calcula el peso total del camino tentativo **y si este paso excede a $c$, no continues explorando este camino**.
- Actualizar la arista de peso maximo si $c(u \to v) >$ "la arista de peso maximo registrada $u$"
- Al final del proceso, el diccionario de la arista máxima contiene la arista de mayor peso en el camino más corto para cada vertice desde el inicio sin exceder la cota $c$ que es lo solicitado en la consigna.
- Muchos detalles fueron omitidos en esta explicación, porque el comportamiento es dijkstra con unas modificaciones.
```python
import heapq # Cola de prioridad
def dijkstra_con_cota_y_maxima_arista(grafo, vertice_inicio, c):
# Diccionario para almacenar las distancias más cortas a cada vértice
distancias = {vertice: float('infinity') for vertice in grafo}
# Diccionario para almacenar la arista máxima en el camino a cada vértice [ALGORITMO MODIFICADO]: Almacena la arista de peso máximo encontrada en el camino hacia cada nodo.
max_arista = {vertice: 0 for vertice in grafo}
# La distancia al vértice inicial es 0
distancias[vertice_inicio] = 0
# Cola de prioridad para gestionar los vértices a explorar, incluyendo la arista máxima en el camino [ALGORITMO MODIFICADO]: Se modifica para incluir el peso de la arista máxima actual en el camino.
cola_prioridad = [(0, vertice_inicio, 0)]
while cola_prioridad:
# Extraer el vértice con la menor distancia y la arista máxima hasta ese punto [ALGORITMO MODIFICADO]: Se extrae también la arista máxima actual.
distancia_actual, vertice_actual, arista_max_actual = heapq.heappop(cola_prioridad)
# Los nodos pueden agregarse varias veces a la cola de prioridad.
# Solo procesamos un vértice la primera vez que lo sacamos de la cola.
if distancia_actual > distancias[vertice_actual]:
continue
# Considerar todos los vecinos adyacentes del vértice actual
for vecino, peso in grafo[vertice_actual].items():
distancia = distancia_actual + peso
arista_max = max(arista_max_actual, peso) # [ALGORITMO MODIFICADO]: Actualiza la arista máxima si la nueva arista es mayor.
# Comprobar si la distancia total aún se mantiene por debajo de la cota c [ALGORITMO MODIFICADO]: No continuar si la distancia excede la cota.
if distancia > c:
continue
# Solo considerar este nuevo camino si es mejor y no excede la cota c [ALGORITMO MODIFICADO]: Considera el camino si es más corto y respeta la cota.
if distancia < distancias[vecino] or (distancia == distancias[vecino] and arista_max > max_arista[vecino]):
distancias[vecino] = distancia
max_arista[vecino] = arista_max # [ALGORITMO MODIFICADO]: Actualiza la arista máxima en el diccionario.
heapq.heappush(cola_prioridad, (distancia, vecino, arista_max)) # [ALGORITMO MODIFICADO]: Añade a la cola con la arista máxima.
return distancias, max_arista # [ALGORITMO MODIFICADO]: Devuelve también las aristas máximas.
```
- Imagen de ejemplo:
- 
### Demostración de correctitud
- Definiciones de variables y conceptos a utilizar:
- $G$: Grafo ponderado donde cada vértice está conectado a otro vértices mediante aristas que tienen un PESO asociado.
- Vértice de origen $s$: Punto de partida de Dijkstra dondeo se calculan las distancias minimas a todos los otros vértices.
- Conjunto $R$: Conjunto de vertices que para los cuales se han determinado y fijado definitivamente las distancias mínimas desde el vertice de origen $s$. $R$ Empieza vacío.
- Distancia $d(v)$: Representa la distancia más corta conocida desde $s$ hasta el vértice $v$ en cualquier punto dado del algoritmo.
- Distancia mínima $\delta (v)$: La verdadera distancia mínima del camino más corto desde $s$ hasta $v$.
- cota $c$: limite superior para la suma de los pesos de las aristas en cualquier camino del digrafo.
- **Lema 1:** Distancia en $R$
- Sí un vértice $x \in R \Rightarrow d(x)=\delta(x) \ \land \ d(x) \leq c$
- Este lema asegura que para cada vez que un vértice es añadido a $R$, su distancia es no solo la minima hasta ese punto, además que también está dentro de la cota $c$.
- **Lema 2:** validación de caminos
- Para cualquier vértice $u$ seleccionado para ser añadido a $R$, no existe un camino $s$ a $u$ con longitud menor a $d(u)$ que cumpla con la cota $c$.
- Si huibiera un camino más corto que cumpliera con $c$, entonces ese camino implicaría una distancia más corta que contradiría a la suposición de que las distancias en $R$ son mínimas y cumplen con $c$.
- Voy a hacer la demostración por inducción y me ayudé mediante una [prueba hecha en la universidad estatal de Oregon](https://web.engr.oregonstate.edu/~glencora/wiki/uploads/dijkstra-proof.pdf)
- Caso base:
- $|R|=1$, al principio $R = \{s\} \ \land d(s) = 0$ que es correcto porque la distancia de $s$ a sí mismo es $0$, y $0 \leq c$ cumple con la cota.
- Hipotesis inductiva:
- Suposición para $R$: Asumimos que para cada $x \in R$ dado, al final de cada iteración del algoritmo se cumple que:
- $d(x) = \delta(x)$: La distancia registrada $d(x)$ es igual a la distancia minima $\delta(x)$
- $d(x) \leq c$: La distancia $d(x)$ no excede a la cota $c$. Esto implica que todas las distancias registradas en $R$ son validades no solo por ser las mínimas posibles, sino por también estar dentro del límite establecido por $c$.
- Definición de $R'$: sea $R$ lo previamente escrito.
- Y sea $u$ el último vértice añadido a $R$, formando $R' = R \cup \{u\}$. Nuestra HI es que $\forall x \in R', d(x) = \delta(x) \ \land \ d(x) \leq c$.
- Paso inductivo:
- Asumo la HI **verdadera** para $R$.
- O sea que: $$\forall x \in R, d(x)= \delta(x) \ \land \ d(x) \leq c$$ **verdadera**.
- Ahora **QVQ** la HI para $R'$ se cumple.
- Asumo: $\forall x \in R, d(x)= \delta(x) \ \land \ d(x) \leq c$ que es cierto.
- Para demostrarlo en $R'$:
- Al añadir $u$ a $R$ para formar $R'$, hay que demostrar:
- $$d(u)= \delta(u) \ \land \ d(u) \leq c$$
- Por el **Lema 2** se demuestra que: No existe un camino más corto dentro de la cota $c$ que el registrado como $d(u)$
- Por el **Lema 1**: Al formar $R'$ agregando $u$, aplicamos el Lema 1 para validar las distancias y que no alcance la cota. $d(u)= \delta(u) \ \land \ d(u) \leq c$.
- Verificación para cada $v$ adyacente a $u$:
- Si se encuentra una distancia menor para algún vértice $v$ adyacente a $u$, que también cumpla con la cota $c$ ej: $d(u)+ c(u \to v) \leq c$, entonces $d(v)$ será actualizada.
- El lema 1 se aplica para asegurar que estas nuevas distancias actualizadas cumplen con ser minimas y que se mantengan dentro de la cota $c$.
- Al final de este proceso para $R'$, garantiza que cada vertice en $R'$ incluyendo el recién agregado $u$, tiene una distancia que es la minima posible como adherente a la cota $c$, y esto era lo que queriamos probar. $\square$