Punto 1: Problema de camino mínimo

El problema clásico de camino mínimo consiste en, dado un grafo $G = (V, E)$ dirigido o no dirigido con una función de peso $w : E \to \R$ y un vértices $s \in V$, encontrar el peso mínimo del camino de $s$ a $v$, para todo $v \in V$. A este problema lo denominamos camino mínimo de una sóla fuente (source).

Para esto podemos dar ciertas definiciones que nos ayudan a formalizar el problema:

• El peso de un camino $p = \langle v_0, ..., v_k\rangle$ en $G$ lo definimos como:

  $$ w(p) = \sum_{i=1}^k w(v_{i-1}, v_i) $$

• El peso mínimo para dos nodos $u, v \in V$ está definido como:

  $$ \delta(u,v) = \begin{cases} \min\{w(p) : u \stackrel{p}{\leadsto} v\} \qquad&\text{si hay camino de $u$ a $v$} \\ \infty \qquad&\text{caso contrario} \end{cases} $$

• Un camino mínimo de $u$ a $v$ es entonces, para todo par de nodos $u,v \in V$, un camino $p$ de $u$ a $v$ tal que $w(p) = \delta(u,v)$.

Dado un grafo $G = (V, E)$ dirigido con una función de peso $w : E \to \R$, este problema tiene ciertas variantes:

• Dado un vértice $t$ como destinación, calcular el camino mínimo de todo vértice $u \in V$ a $t$. Este problema se denomina camino mínimo de destinación única. Si invertimos la dirección de las aristas podemos resolverlo como un problema de camino mínimo de una sola fuente.
• Dados dos vértices $u, v \in V$, se busca encontrar el camino mínimo de $u$ a $v$. A este problema lo denominamos camino mínimo de un par. Todos los algoritmos que conocemos para resolver este problema tienen asintóticamente la misma complejidad temporal que el problema genérico de una sola fuente.
• Por último también puede ser de interés buscar el camino mínimo de $u$ a $v$, para todo par de nodos $u, v \in V$. Este problema se denomina de camino mínimo de todos los pares.

Es posible modelar otros problemas en término de problemas de camino mínimo. Por ejemplo podemos pensar el problema de llegar de un punto (intersección de calles) $s$ de la ciudad a otro $v$, siguiendo las rutas válidas marcadas en el mapa. Si modelamos el problema como un grafo donde cada intersección es un nodo, cada cuadra es una arista y el tránsito de cada cuadra lo representamos como un número real, podremos pensar el camino mínimo del vértice que representa $s$ al que representa a $v$ como un camino que minimiza el tránsito.

El algoritmo de Floyd-Warshall resuelve el problema de camino mínimo de todos los pares. Para esto, pensamos al problema como un problema de programación dinámica.

El problema de camino mínimo presenta subestructura óptima, ya que los subcaminos de un camino mínimo son a su vez caminos mínimos. Más aún, el algoritmo de Floyd-Warshall se basa en la observación de que, si tenemos un camino mínimo $p$ de $i$ a $j$ cuyos vértices intermedios son tomados del subconjunto $\{1, …, k\} \subseteq V$, tenemos dos escenarios:

• O bien $k$ es un vértice intermedio de $p$, en cuyo caso podemos desarmar $p$ en $i \stackrel{p_{ik}}{\leadsto} k \stackrel{p_{kj}}{\leadsto} j$ y observar que $p_{ik}$ es un camino mínimo entre $i$ y $k$ cuyos vértices intermedios son tomados del conjunto $\{1, … k - 1\} \subseteq V$ y análogamente $p_{kj}$ es un camino mínimo entre $k$ y $j$ cuyos vértices intermedios son tomados de $\{1, … k - 1\} \subseteq V$;
• O bien $k$ no es un vértice intermedio de $p$ y entonces podemos afirmar que $p$ es un camino mínimo de $i$ a $j$ cuyos vértices son tomados del conjunto $\{1, … k - 1\} \subseteq V$.

Entonces, dado un grafo $G = (V, E)$ con su función de peso $w : E \to \R$, vamos a extenderla a una matriz $W \in \R^{n \times n}$ donde $n = |V|$, definida por