# TDA | Practica 5 ejercicio 3
## Consigna
- Diseñar un algoritmo eficiente que, dado un digrafo pesado $G$ y dos vértices $s$ y $t$, determine el recorrido minimo de $s$ a $t$ **que pasa por a lo sumo una arista de peso negativo**.
- Demostrar correctitud.
## Resolución
- Saco las aristas negativas de $G$ y lo llamo $H$
- Traspongo $H$ y lo llamo $H_t$ para poder usarlo en el algoritmo de Dijkstra invertido.
- Calculo el camino más corto en $H$ desde inicio.
- Calculo el camino más corto en $H_t$ desde fin.
- Evaluo la distancia minima inicialmente sin aristas negativas con el camino más corto desde el inicio hasta el fin.
- Para cada arista negativa, calculo si hay un camino más corto reintroduciendo cada arista.
- Actualizo la distancia mínima si encuentro un camino más corto
- Devuelvo la distancia minima
- $O((n+m) \ log \ n)$
#### Por una cuestión de legibilidad reduzco las auxiliares a parte.
### Código
```python
import networkx as nx
def main(grafo, aristas, inicio, fin):
# Crear el grafo dirigido y añadir aristas
G = nx.DiGraph()
G.add_weighted_edges_from(aristas)
# Identificar aristas negativas
aristasNegativas = [(u, v, w) for u, v, w in aristas if w < 0]
# Crear el grafo H sin aristas negativas
H = sacarAristas(G, aristasNegativas)
# Trasponer el grafo H
H_t = trasponer(H)
# Calcular distancias más cortas desde inicio en H y hacia fin en H_t
D1 = dijkstra(H, inicio)
D2 = dijkstra(H_t, fin)
# Evaluar la distancia mínima inicialmente sin aristas negativas
if fin not in D1:
distanciaMinima = float('inf') # No hay camino directo
else:
distanciaMinima = D1[fin]
# Evaluar los efectos de reintroducir cada arista negativa
for u, v, peso in aristasNegativas:
if u in D1 and v in D2: # Asegurar que ambos nodos son alcanzables
nuevaDistancia = D1[u] + peso + D2[v]
distanciaMinima = min(distanciaMinima, nuevaDistancia)
return distanciaMinima
```
### Auxiliares
```python
import networkx as nx
def sacarAristas(G, aristasNegativas):
""" Elimina aristas especificadas de G y devuelve el nuevo grafo """
H = G.copy()
for u, v, _ in aristasNegativas:
if H.has_edge(u, v):
H.remove_edge(u, v)
return H
def trasponer(H):
""" Devuelve el grafo transpuesto de H """
return nx.reverse(H, copy=True)
def dijkstra(G, nodo_inicio):
""" Utiliza NetworkX para calcular las distancias más cortas desde nodo_inicio """
return nx.single_source_dijkstra_path_length(G, nodo_inicio)
```
## Demostración
- Diseñar un algoritmo eficiente que, dado un digrafo pesado $G$ y dos vértices $s$ y $t$, determine el recorrido minimo de $s$ a $t$ **que pasa por a lo sumo una arista de peso negativo**.
- La solución optima y lo que devuelve el algoritmo son:
- Solución:
- $recorridoMinimo(G,s,t)$ = $min${*Pesos de todos los caminos que no tienen aristas negativas, pesos de todos los caminos con exactamente una arista negativa*}
- llamo $P^+$ a los pesos que no tiene una arista negativa.
- llamo $P^-$ a los pesos que tienen una arista negativa.
- Algoritmo:
- `distanciaMinima = min(distanciaMinima, nuevaDistancia)`
- siendo la distancia minima el peso minimo de camino sin la arista negativa.
- la nueva distancia es justamente son los pesos de los caminos con una arista negativa. Dado como $nuevaDistancia = D_1[u] + peso(u,v) + D_2[v]$
- $D_1 =$ `dijkstra(H, inicio)`
- $D_2 =$ `dijkstra(H_t, fin)`
- Notar que $min(P^+)=$ `distanciaMinima` es trivial ya que $P^+$ es el mismo peso mínimo del camino sin aristas negativas
- Ahora para probar que $P^-$ = `nuevaDistancia`:
- `min(nuevaDistancia)` $\geq P^- \ \land$ `min(nuevaDistancia)` $\leq min(P^-)$
- Primero:
- `min(nuevaDistancia)` $\geq P^-$: Como en `min(nuevaDistancia)` tenemos que los pesos de los caminos con una arista negativa tal que los costos de $D_1$ y $D_2$ son minimas, sabemos que estará incluido en los pesos de todos los caminos que tienen exactamente 1 arista negativa.
- $\therefore$ `nuevaDistancia` $\subseteq \ P^- \Rightarrow$ `min(nuevaDistancia)` $\geq P^-$, todo elemento en `nuevaDistancia` está en $P^-$, el minimo de $P^-$, será al menos tan chico como el minimo de nuevaDistancia que tiene menos elementos, con lo que probamos `min(nuevaDistancia)` $\geq P^-$
- Segundo
- `min(nuevaDistancia)` $\leq min(P^-)$: Dado que `nuevaDistancia` considera especificamente la re-introducción de cada arista negativa individual en los caminos óptimos calculados sin aristas negativas, y dado que este enfoque garantiza que se evalúa el impacto de cada arista negativa en el contexto de camino minimo incluyendola, entonces `nuevaDistancia` necesariamente incluye el minimo de todos los caminos que contienen exactamente una arista negativa.
- Cada `nuevaDistancia` es calculada como: la suma del camino más corto de $s$ a $u$, el peso de la arista negativa $(u,v)$ y el camino más corto de $v$ a $t$ en el grafo trapuesto.
- Esto asegura que estamos considerando el impacto total mínimo de re-introducir esa arista negativa especifica.
- Por lo tanto el mínimo de todos estos valores ya calculados será menos o igual que cualquier otro camino que contenga exactamente una arista negativa porque consideramos iterativamente los caminos posibles para cada segmento del camino.
- Entonces así `min(nuevaDistancia)` $\leq min(P^-)$ que es lo que queríamos probar.
- Entonces si probamos que:
- `min(nuevaDistancia)` $\geq P^- \ \land$ `min(nuevaDistancia)` $\leq min(P^-)$
- Podemos decir que `min(nuevaDistancia)` = P^-$
- Que es justamente lo que queriamos probar, que nuestro algoritmo nos de la solución optima$\square$