Algoritmo paralelo de ruta más corta desde un único origen

Un problema central en la teoría algorítmica de grafos es el problema del camino más corto . Una de las generalizaciones del problema del camino más corto se conoce como el problema de los caminos más cortos de origen único (SSSP) , que consiste en encontrar los caminos más cortos desde un vértice de origen.${\displaystyle s}$a todos los demás vértices del grafo. Existen algoritmos secuenciales clásicos que resuelven este problema, como el algoritmo de Dijkstra . En este artículo, sin embargo, presentamos dos algoritmos paralelos que lo resuelven.

Otra variación del problema es el problema de los caminos más cortos entre todos los pares (APSP, por sus siglas en inglés), que también tiene enfoques paralelos: Algoritmo paralelo de caminos más cortos entre todos los pares .

Dejar${\displaystyle G=(V,E)}$ser un grafo dirigido con${\displaystyle |V|=n}$nodos y${\displaystyle |E|=m}$bordes. Deja${\displaystyle s}$ser un vértice distinguido (llamado "fuente") y${\displaystyle c}$sea ​​una función que asigne un peso real no negativo a cada arista. El objetivo del problema de los caminos más cortos desde una única fuente es calcular, para cada vértice${\displaystyle v}$accesible desde${\displaystyle s}$, el peso de una ruta de peso mínimo desde${\displaystyle s}$a${\displaystyle v}$, denotado por${\displaystyle \operatorname {dist} (s,v)}$y abreviado${\displaystyle \operatorname {dist} (v)}$El peso de un camino es la suma de los pesos de sus aristas. Establecemos${\displaystyle \operatorname {dist} (u,v):=\infty }$si${\displaystyle v}$es inaccesible desde${\displaystyle u}$. ^{[ 1 ]}

Los algoritmos de ruta más corta secuencial suelen aplicar métodos de etiquetado iterativos basados ​​en el mantenimiento de una distancia tentativa para todos los nodos;${\displaystyle \operatorname {tent} (v)}$siempre es${\displaystyle \infty }$o el peso de algún camino desde${\displaystyle s}$a${\displaystyle v}$y por lo tanto un límite superior en${\displaystyle \operatorname {dist} (v)}$Las distancias tentativas se mejoran realizando relajaciones de borde, es decir, para un borde${\displaystyle (v,w)\in E}$ el algoritmo establece${\displaystyle \operatorname {tent} (w):=\min\{\operatorname {tent} (w),\operatorname {tent} (v)+c(v,w)\}}$. ^{[ 1 ]}

Para todos los algoritmos paralelos, asumiremos un modelo PRAM con lecturas y escrituras concurrentes.

El algoritmo de pasos delta es un algoritmo de corrección de etiquetas, lo que significa que la distancia tentativa de un vértice se puede corregir varias veces mediante relajaciones de aristas hasta el último paso del algoritmo, cuando todas las distancias tentativas quedan fijas.

El algoritmo mantiene nodos elegibles con distancias tentativas en una matriz de cubetas, cada una de las cuales representa un rango de distancia de tamaño${\displaystyle \Delta }$Durante cada fase, el algoritmo elimina todos los nodos del primer cubo no vacío y relaja todos los bordes salientes de peso máximo${\displaystyle \Delta }$. Los bordes de mayor peso solo se relajan después de que sus respectivos nodos iniciales estén firmemente establecidos. ^{[ 1 ]} El parámetro ${\displaystyle \Delta }$es un número real positivo que también se denomina "ancho de paso" o "ancho de cubeta". ^{[ 1 ]}

El paralelismo se obtiene eliminando simultáneamente todos los nodos del primer cubo no vacío y relajando sus bordes de luz salientes en una sola fase. Si un nodo${\displaystyle v}$ha sido eliminado del cubo actual${\displaystyle B[i]}$con un valor de distancia no final entonces, en alguna fase posterior,${\displaystyle v}$eventualmente será reinsertado en${\displaystyle B[i]}$y los bordes de luz salientes de${\displaystyle v}$ se volverán a relajar. Los bordes pesados ​​restantes que emanan de todos los nodos que se han eliminado de${\displaystyle B[i]}$hasta ahora se han relajado de una vez por todas cuando${\displaystyle B[i]}$finalmente queda vacío. Posteriormente, el algoritmo busca el siguiente cubo no vacío y procede como se describió anteriormente. ^{[ 1 ]}

El peso máximo de la ruta más corta para el nodo de origen${\displaystyle s}$se define como${\displaystyle L(s):=\max\{\operatorname {dist} (s,v):\operatorname {dist} (s,v)<\infty \}}$, abreviado${\displaystyle L}$. ^{[ 1 ]} Además, el tamaño de un camino se define como el número de aristas en el camino.

Distinguimos los bordes ligeros de los bordes pesados, donde los bordes ligeros tienen un peso máximo${\displaystyle \Delta }$ y los bordes pesados ​​tienen un peso mayor que${\displaystyle \Delta }$.

A continuación se presenta el algoritmo de pasos delta en pseudocódigo:

1 por cada${\displaystyle v\in V}$hacer${\displaystyle \operatorname {tent} (v):=\infty }$ 2 ${\displaystyle relax(s,0)}$; (*Insertar nodo de origen con distancia 0*) 3 mientras${\displaystyle \lnot isEmpty(B)}$hacer (*Fase A: Algunos nodos en cola quedaron (a)*) 4 ${\displaystyle i:=\min\{j\geq 0:B[j]\neq \emptyset \}}$ (*Cubo no vacío más pequeño (b)*) 5 ${\displaystyle R:=\emptyset }$ (*Aún no se han eliminado nodos para el bucket B[i]*) 6 mientras${\displaystyle B[i]\neq \emptyset }$hacer (*Nueva fase (c)*) 7 ${\displaystyle Req:=findRequests(B[i],light)}$ (*Crear solicitudes para bordes claros (d)*) 8 ${\displaystyle R:=R\cup B[i]}$ (*Recuerde los nodos eliminados (e)*) 9 ${\displaystyle B[i]:=\emptyset }$ (*Cubo actual vacío*) 10 ${\displaystyle relaxRequests(Req)}$ (*Realice relajaciones, los nodos pueden (re)entrar en B[i] (f)*) 11 ${\displaystyle Req:=findRequests(R,heavy)}$ (*Crear solicitudes para bordes gruesos (g)*) 12 ${\displaystyle relaxRequests(Req)}$ (*Las relajaciones no recargarán B[i] (h)*) 13 14 función${\displaystyle findRequests(V',kind:\{{\text{light}},{\text{heavy}}\})}$:conjunto de solicitud 15 regresos${\displaystyle \{(w,\operatorname {tent} (v)+c(v,w)):v\in V'\land (v,w)\in E_{\text{kind}}\}}$ 16 17 procedimiento${\displaystyle relaxRequests(Req)}$ 18 por cada uno${\displaystyle (w,x)\in Req}$hacer${\displaystyle relax(w,x)}$ 19 20 procedimiento${\displaystyle relax(w,x)}$ (*Insertar o mover w en B si${\displaystyle x<\operatorname {tent} (w)}$*) 21 si${\displaystyle x<\operatorname {tent} (w)}$entonces 22 ${\displaystyle B[\lfloor \operatorname {tent} (w)/\Delta \rfloor ]:=B[\lfloor \operatorname {tent} (w)/\Delta \rfloor ]\setminus \{w\}}$ (*Si está dentro, retírelo del cubo viejo*) 23 ${\displaystyle B[\lfloor x/\Delta \rfloor ]:=B[\lfloor x/\Delta \rfloor ]\cup \{w\}}$ (*Insertar en un nuevo depósito*) 24 ${\displaystyle \operatorname {tent} (w):=x}$

Ejemplo

A continuación se describe paso a paso la ejecución del algoritmo para un pequeño ejemplo de grafo. El vértice de origen es el vértice A y${\displaystyle \Delta }$es igual a 3.

Al inicio del algoritmo, todos los vértices, excepto el vértice de origen A, tienen distancias tentativas infinitas.

Balde${\displaystyle B[0]}$tiene rango${\displaystyle [0,2]}$, balde${\displaystyle B[1]}$tiene rango${\displaystyle [3,5]}$y cubo${\displaystyle B[2]}$tiene rango${\displaystyle [6,8]}$.

El cubo${\displaystyle B[0]}$Contiene el vértice A. Todos los demás cubos están vacíos.

El algoritmo relaja todos los bordes de luz incidentes a${\displaystyle B[0]}$, que son las aristas que conectan A con B, G y E.

Los vértices B, G y E se insertan en el cubo.${\displaystyle B[1]}$. Desde${\displaystyle B[0]}$Todavía está vacío, el borde grueso que conecta A con D también está relajado.

Ahora los bordes de luz incidentes a${\displaystyle B[1]}$están relajados. El vértice C se inserta en el cubo${\displaystyle B[2]}$Desde ahora${\displaystyle B[1]}$Si está vacío, el borde grueso que conecta E con F puede relajarse.

En el siguiente paso, el cubo${\displaystyle B[2]}$Se examina, pero no conlleva ninguna modificación de las distancias tentativas.

El algoritmo finaliza.

Para el algoritmo de pasos de radio, debemos asumir que nuestro gráfico${\displaystyle G}$no tiene dirección.

La entrada al algoritmo es un grafo no dirigido ponderado, un vértice de origen y un valor de radio de destino para cada vértice, dado como una función.${\displaystyle r:V\rightarrow \mathbb {R} _{+}}$. ^{[ 3 ]} El algoritmo visita los vértices en distancia creciente desde la fuente${\displaystyle s}$En cada paso${\displaystyle i}$, el incremento de radio aumenta el radio centrado en${\displaystyle s}$de${\displaystyle d_{i-1}}$a${\displaystyle d_{i}}$y resuelve todos los vértices${\displaystyle v}$en el anillo${\displaystyle d_{i-1}<d(s,v)\leq d_{i}}$. ^{[ 3 ]}

A continuación se muestra el algoritmo de incremento de radio en pseudocódigo:

Entrada : Un gráfico${\displaystyle G=(V,E,w)}$radios de vértice${\displaystyle r(\cdot )}$y un nodo fuente${\displaystyle s}$Salida : Las distancias del gráfico${\displaystyle \delta (\cdot )}$de${\displaystyle s}$. 1 ${\displaystyle \delta (\cdot )\leftarrow +\infty }$,${\displaystyle \delta (s)\leftarrow 0}$ 2 por cada uno${\displaystyle v\in N(s)}$hacer${\displaystyle \delta (v)\leftarrow w(s,v)}$,${\displaystyle S_{0}\leftarrow \{s\}}$,${\displaystyle i\leftarrow 1}$ 3 mientras${\displaystyle |S_{i-1}|<|V|}$hacer 4 ${\displaystyle d_{i}\leftarrow \min _{v\in V\setminus S_{i-1}}\{\delta (v)+r(v)\}}$ 5 repetir 6 para cada uno${\displaystyle u\in V\setminus S_{i-1}}$calle${\displaystyle \delta (u)\leq d_{i}}$hacer 7 por cada${\displaystyle v\in N(u)\setminus S_{i-1}}$hacer 8 ${\displaystyle \delta (v)\leftarrow \min\{\delta (v),\delta (u)+w(u,v)\}}$ 9 hasta que no${\displaystyle \delta (v)\leq d_{i}}$fue actualizado 10 ${\displaystyle S_{i}=\{v\;|\;\delta (v)\leq d_{i}\}}$ 11 ${\displaystyle i=i+1}$ 12 regresos${\displaystyle \delta (\cdot )}$

A pesar de${\displaystyle S\subseteq V}$, definir${\displaystyle N(S)=\bigcup _{u\in S}\{v\in V\mid d(u,v)\in E\}}$ser el conjunto de vecinos de S. Durante la ejecución de la búsqueda en anchura estándar o el algoritmo de Dijkstra , la frontera es el conjunto de vecinos de todos los vértices visitados. ^{[ 3 ]}

En el algoritmo de pasos de radio, una nueva distancia de ronda${\displaystyle d_{i}}$se decide en cada ronda con el objetivo de limitar el número de subpasos. El algoritmo toma un radio${\displaystyle r(v)}$para cada vértice y selecciona un${\displaystyle d_{i}}$en el paso${\displaystyle i}$tomando el mínimo${\displaystyle \delta (v)+r(v)}$en general${\displaystyle v}$en la frontera (Línea 4).

Las líneas 5-9 luego ejecutan los subpasos de Bellman-Ford hasta que todos los vértices con radio menor que${\displaystyle d_{i}}$están establecidos. Vértices dentro${\displaystyle d_{i}}$Luego se añaden al conjunto visitado.${\displaystyle S_{i}}$. ^{[ 3 ]}

Ejemplo

A continuación se describe paso a paso la ejecución del algoritmo para un pequeño ejemplo de grafo. El vértice de origen es el vértice A y el radio de cada vértice es igual a 1.

Al comienzo del algoritmo, todos los vértices, excepto el vértice de origen A, tienen distancias tentativas infinitas, denotadas por${\displaystyle \delta }$en el pseudocódigo.

Todos los vecinos de A están relajados y${\displaystyle S_{0}=\{A\}}$.

La variable${\displaystyle d_{1}}$se elige que sea igual a 4 y los vecinos de los vértices B, E y G se relajan.${\displaystyle S_{1}=\{A,B,E,G\}}$

La variable${\displaystyle d_{2}}$se elige que sea igual a 6 y no se modifican los valores.${\displaystyle S_{2}=\{A,B,C,D,E,G\}}$.

La variable${\displaystyle d_{3}}$se elige que sea igual a 9 y no se modifican los valores.${\displaystyle S_{3}=\{A,B,C,D,E,F,G\}}$.

El algoritmo finaliza.