Número de caminos de longitud fija / Caminos más cortos de longitud fija

El siguiente artículo describe soluciones a estos dos problemas construidas sobre la misma idea: reducir el problema a la construcción de una matriz y calcular la solución con la multiplicación de matrices usual o con una multiplicación modificada.

Número de caminos de una longitud fija

Nos dan un grafo dirigido, no ponderado $G$ con $n$ vértices y nos dan un entero $k$. La tarea es la siguiente: para cada par de vértices $(i, j)$ hay que encontrar el número de caminos de longitud $k$ entre estos vértices. Los caminos no tienen que ser simples, es decir, los vértices y las aristas se pueden visitar cualquier número de veces en un solo camino.

Asumimos que el grafo se especifica con una matriz de adyacencia, es decir, la matriz $G[][]$ de tamaño $n \times n$, donde cada elemento $G[i][j]$ es igual a $1$ si el vértice $i$ está conectado con $j$ por una arista, y $0$ si no están conectados por una arista. El siguiente algoritmo también funciona en el caso de aristas múltiples: si algún par de vértices $(i, j)$ está conectado con $m$ aristas, entonces podemos registrar esto en la matriz de adyacencia poniendo $G[i][j] = m$. También el algoritmo funciona si el grafo contiene bucles (un bucle es una arista que conecta un vértice consigo mismo).

Es obvio que la matriz de adyacencia construida es la respuesta al problema para el caso $k = 1$. Contiene el número de caminos de longitud $1$ entre cada par de vértices.

Construiremos la solución de forma iterativa: Supongamos que conocemos la respuesta para algún $k$. Aquí describimos un método para construir la respuesta para $k + 1$. Denotemos por $C_k$ la matriz para el caso $k$, y por $C_{k+1}$ la matriz que queremos construir. Con la siguiente fórmula podemos calcular cada entrada de $C_{k+1}$:

$$C_{k+1}[i][j] = \sum_{p = 1}^{n} C_k[i][p] \cdot G[p][j]$$

Es fácil ver que la fórmula no calcula otra cosa que el producto de las matrices $C_k$ y $G$:

$$C_{k+1} = C_k \cdot G$$

Así, la solución del problema se puede representar de la siguiente forma:

$$C_k = \underbrace{G \cdot G \cdots G}_{k \text{ times}} = G^k$$

Resta notar que los productos de matrices se pueden elevar a una potencia alta de forma eficiente usando exponenciación binaria. Esto da una solución con complejidad $O(n^3 \log k)$.

Caminos más cortos de una longitud fija

Nos dan un grafo dirigido ponderado $G$ con $n$ vértices y un entero $k$. Para cada par de vértices $(i, j)$ hay que encontrar la longitud del camino más corto entre $i$ y $j$ que consiste de exactamente $k$ aristas.

Asumimos que el grafo se especifica por una matriz de adyacencia, es decir, vía la matriz $G[][]$ de tamaño $n \times n$ donde cada elemento $G[i][j]$ contiene la longitud de las aristas del vértice $i$ al vértice $j$. Si no hay arista entre dos vértices, entonces el elemento correspondiente de la matriz se asignará a infinito $\infty$.

Es obvio que en esta forma la matriz de adyacencia es la respuesta al problema para $k = 1$. Contiene las longitudes de los caminos más cortos entre cada par de vértices, o $\infty$ si no existe un camino que consista de una arista.

Otra vez podemos construir la solución al problema de forma iterativa: Supongamos que conocemos la respuesta para algún $k$. Mostramos cómo podemos calcular la respuesta para $k+1$. Denotemos $L_k$ la matriz para $k$ y $L_{k+1}$ la matriz que queremos construir. Entonces la siguiente fórmula calcula cada entrada de $L_{k+1}$:

$$L_{k+1}[i][j] = \min_{p = 1 \ldots n} \left(L_k[i][p] + G[p][j]\right)$$

Al mirar más de cerca esta fórmula, podemos trazar una analogía con la multiplicación de matrices: de hecho la matriz $L_k$ se multiplica por la matriz $G$, la única diferencia es que en lugar de la operación de multiplicación tomamos el mínimo en lugar de la suma, y la suma en lugar de la multiplicación como operación interna.

$$L_{k+1} = L_k \odot G,$$

donde la operación $\odot$ se define de la siguiente forma:

$$A \odot B = C~~\Longleftrightarrow~~C_{i j} = \min_{p = 1 \ldots n}\left(A_{i p} + B_{p j}\right)$$

Así, la solución de la tarea se puede representar usando la multiplicación modificada:

$$L_k = \underbrace{G \odot \ldots \odot G}_{k~\text{times}} = G^{\odot k}$$

Resta notar que también podemos calcular esta exponenciación de forma eficiente con exponenciación binaria, porque la multiplicación modificada es obviamente asociativa. Así que también esta solución tiene complejidad $O(n^3 \log k)$.

Generalización de los problemas para caminos con longitud hasta $k$ {data-toc-label=“Generalización de los problemas para caminos con longitud hasta k”}

Las soluciones de arriba resuelven los problemas para un $k$ fijo. Sin embargo las soluciones se pueden adaptar para resolver problemas en los que se permite que los caminos contengan no más de $k$ aristas.

Esto se puede hacer modificando ligeramente el grafo de entrada.

Duplicamos cada vértice: para cada vértice $v$ creamos un vértice más $v’$ y agregamos la arista $(v, v’)$ y el bucle $(v’, v’)$. El número de caminos entre $i$ y $j$ con a lo sumo $k$ aristas es el mismo número que el número de caminos entre $i$ y $j’$ con exactamente $k + 1$ aristas, ya que hay una biyección que mapea cada camino $[p_0 = i,p_1,\ldots,~p_{m-1},~p_m = j]$ de longitud $m \le k$ al camino $[p_0 = i,p_1,\ldots,~p_{m-1},~p_m = j, j’, \ldots, j’]$ de longitud $k + 1$.

El mismo truco se puede aplicar para calcular los caminos más cortos con a lo sumo $k$ aristas. Otra vez duplicamos cada vértice y agregamos las dos aristas mencionadas con peso $0$.