# TDA | Practica 5 ejercicio 1 ## Enunciado 1. Dado un digrafo $D$ con pesos $c:E(D)\to\mathbb{N}$ y dos vértices $s$ y $t$, decimos que una arista $v\to w$ es $st$-$e\textit{ficiente cuando }v\to w\text{ pertenece a alg\'{u} n camino m\'{ı } nimo de }s$ a $t$. Sea $d(\cdot,\cdot)$ la función que indica el peso de un camino mínimo entre dos vértices. $a.$ Demostrar que $v\to w$ es $st$-eficiente si y sólo si $d(s,v)+c(v\to w)+d(w,t)=d(s,t).$ $b.$ Usando el inciso anterior, proponga un algoritmo eficiente que encuentre el mínimo de los caminos entre $s$ y $t$ que no use aristas $st$-eficientes. Si dicho camino no existe, el algoritmo retorna $\bot.$ ## Resolución - Nos dan un digrafo pesado - $v \to w$ es eficiente cuando esta arista pertenece a algún camino minimo de $s$ a $t$ - $d(.,.)$ indica el peso de un camino minimo entre dos vertices. ### a) - $v\to w$ es $st$-eficiente $\iff$ $d(s,v)+c(v \to w)+d(w,t)=d(s,t)$. - el primer $d(s,v)$ nos dice el peso del camino minimo entre $s,v$. - $c(v \to w)$ nos da el peso de esa arista $c \to w$. - $d(w,t)$ nos da el peso del camino minimo entre $w$ y $t$. - Esta ecuación indica que pertenece al camino minimo de $s$ a $t$. - Voy a armar la estructura de la demostración. - $v\to w$ es $st$-eficiente $\equiv A$ - $d(s,v)+c(v \to w)+d(w,t)=d(s,t) \ \equiv B$ - $A \iff B$ - Divido la demostración en partes: - $\Rightarrow)$ Quiero probar que $A \Rightarrow$ $B$, asumo $A$ verdadero - $\Leftarrow$) Quiero probar que $B \Rightarrow$ $A$, asumo $B$ verdadero - $\Rightarrow)$ $v\to w$ es $st$-eficiente, entonces $v \to w$ pertenece a algún camino minimo de $s$ a $t$. - Voy a asumir $B$ como verdadero y que entonces $A \Rightarrow B$. Lo cual significa que pertenece a algún camino mínimo de $s$ a $t$. - Voy a construir un camino mínimo que incluye $v \to w$: - sea el camino minimo desde $s$ hasta $t$ que pasa por $v$ y luego pasa por $w$. - Este camino se puede describir como la secuencia de aristas de $s$ a $v$, luego la arista $v \to w$ y finalmente las aristas que van de $w$ a $t$. - Por definición de camino mínimo, la suma de los pesos de estas aristas debe ser igual a la distancia minima de $s$ a $t$, o sea $d(s,t)$. - $d(s,v)+c(v \to w)+d(w,t)=d(s,t)$. - $\Leftarrow)$ $v \to w$ pertenece a algún camino mínimo de $s$ a $t$, entonces la arista $v \to w$ es $st$-eficiente. - Asumo verdadera $d(s,v)+c(v \to w)+d(w,t)=d(s,t)$ - Voy a construir un camino: - Si $d(s,v)+c(v \to w)+d(w,t)=d(s,t) = d(s,t)$, sugiere que hay un camino desde $s$ a $t$ que pasa por $v$ y que luego utiliza la arista $v \to w$, que continua desde $w$ a $t$, que su peso total es igual al del peso del camino mínimo. - Conclusión: - Por lo tanto cualquier otro camino que no incluya $v \to w$ y tenga un peso mayor o igual no puede ser camino minimo, implicando que cualquier camino que iguala el peso minimo debe incluir $v \to w$. - Esto significa que $v \to w$ es esencial para alcanzar la distancia mínima entre $s$ y $t$, demostrando que $v \to w$ es $st$-eficiente. ### b) - Dijkstra seguro para calcular la distancia minima $d(s,t)$ - Para cada arista $v \to w$ verifica que si cumple la condición de $st$-eficiencia. - $$d(s,v)+c(v \to w)+d(w,t)=d(s,t)$$ - Guardo las aristas que cumplen esta condición. - Creo una copia del digrafo original y elimino las aristas $st$-eficientes. - Vuelvo a aplicar el algoritmo de camino minimo al grafo modificado. - Si se encuentra un camino, retornar su peso. - Si no se encuentra, retornar indefinido.