Deje un grafo, y dejar que y sea dos vértices de . Podemos degustar una manera eficiente más corto - ruta uniformemente y de forma independiente al azar del conjunto de todos los caminos más cortos entre y ? Por simplicidad, podemos suponer que es simple, no dirigido y no ponderado.s t G s t s t G
Incluso en muchos gráficos restringidos, el número de caminos más cortos entre y puede ser exponencial en el tamaño de . Por lo tanto, naturalmente nos gustaría evitar calcular en realidad todas las rutas - cortas. No sé sobre el caso general, pero me parece que podemos lograr esto para algunas clases especiales de gráficos.t G s t
Esto se siente como algo que alguien debe haber considerado antes. ¿Existe alguna investigación sobre esto, o de hecho es simple de hacer incluso para gráficos generales?
Respuestas:
No estoy 100% seguro de que esta respuesta sea correcta, pero aquí va:
Creo que puede reducir esto a cualquier ruta uniformemente aleatoria, desde , en un DAG con una sola fuente y un solo sumidero.s−t
Dado un gráficoG
Esencialmente, Estoy recogiendo todos los nodos posibles que se pueden utilizar en el camino más corto, y colocándolos en .H
Más sobre cómo funciona esto:
Ahora tenemos un DAG que podemos recorrer de cualquier manera desde , y obtenemos un camino inverso más corto desde s - t . El gráfico debe tener t como única fuente y s como el único sumidero.t−s s−t t s
Si lo anterior es correcto, entonces creo que podemos llevar esto un paso más allá y resolver el problema de la siguiente manera.
Dele a cada nodo en el DAG un peso de nodo; el peso del nodo será el número de rutas desde ese nodo a . Llamemos a esto w ( v ) .s w(v)
Puede calcular rápidamente éstos, véase algoritmo que encuentra el número de caminos simples de s a t en G .
Una vez que tenemos el peso del nodo, podemos elegir uniformemente una ruta de la siguiente manera:
Diseño del DAG como una estructura de nivel (para visualización)En cada nivel, elija un orden arbitrario entre los nodos, es decir. una noción de "izquierda a derecha".fuente
Aquí hay una solución basada en las ideas de la respuesta de Realz Slaw. Básicamente es una reexposición de sus ideas que podría ser más clara o más fácil de seguir. El plan es que procederemos en dos pasos:
En primer lugar, vamos a construir un gráfico con la siguiente propiedad: cualquier camino de s a t en S es una ruta más corta de s a t en G , y cada camino más corto desde s a t en G también está presente en S . Por lo tanto, S contiene exactamente las rutas más cortas en G : todas las rutas más cortas y nada más. Como sucede, S será un DAG.S s t S s t G s t G S S G S
A continuación, vamos a probar de manera uniforme al azar de todos los caminos de a t en S .s t S
Este enfoque generaliza a un gráfico dirigido arbitrario , siempre que todos los bordes tengan un peso positivo, por lo que explicaré mi algoritmo en esos términos. Deje w ( u , v ) denotar el peso en el borde u → v . (Esto generaliza el enunciado del problema que dio. Si tiene un gráfico no ponderado, suponga que cada borde tiene peso 1. Si tiene un gráfico no dirigido, trate cada borde no dirigido ( u , v ) como los dos bordes dirigidos u → v y v → u .)G w(u,v) u→v (u,v) u→v v→u
Paso 1: extracto de .S Ejecute un algoritmo de rutas más cortas de una sola fuente (por ejemplo, el algoritmo de Dijkstra) en , comenzando desde la fuente s . Para cada vértice v en G , supongamos que d ( s , v ) denota la distancia de s a v .G s v G d(s,v) s v
Ahora defina el gráfico siguiente manera. Consiste en cada arista u → v tal que (1) u → v es una arista en G , y (2) d ( s , v ) = d ( s , u ) + w ( u , v ) .S u→v u→v G d(s,v)=d(s,u)+w(u,v)
El gráfico tiene algunas propiedades convenientes:S
Cada ruta más corta de a t en G existe como una ruta en S : una ruta más corta s = v 0 , v 1 , v 2 , … , v k = t en G tiene la propiedad de que d ( s , v i + 1 ) = d ( s , v i ) + w ( v i , v is t G S s=v0,v1,v2,…,vk=t G , por lo que el borde v i → v i + 1 está presente enS.d(s,vi+1)=d(s,vi)+w(vi,vi+1) vi→vi+1 S
Cada camino en de s a t es un camino más corto en G . En particular, considere cualquier ruta en S de s a t , digamos s = v 0 , v 1 , v 2 , ... , v k = t . Su longitud viene dada por la suma de los pesos de sus bordes, a saber, ∑ k i = 1 w ( v i - 1 , v i )S s t G S s t s=v0,v1,v2,…,vk=t ∑ki=1w(vi−1,vi) , pero por la definición de , esta suma es ∑ k i = 1 ( d ( s , v i ) - d ( s , v i - 1 ) , que se telescopía a d ( s , t ) - d ( s , s ) = d ( s , t ) . por lo tanto, este camino es una ruta más corta desde s a t en GS ∑ki=1(d(s,vi)−d(s,vi−1) d(s,t)−d(s,s)=d(s,t) s t G .
Finalmente, la ausencia de bordes de peso cero en implica que S es un dag.G S
Paso 2: muestra una ruta aleatoria. Ahora podemos tirar a la basura los pesos en los bordes en , y muestra un camino al azar de s a t en S .S s t S
Para ayudar con esto, haremos una precomputación para calcular para cada vértice v en S , donde n ( v ) cuenta el número de rutas distintas de v a t . Esta precomputación se puede hacer en tiempo lineal escaneando los vértices de S en orden topológico, utilizando la siguiente relación de recurrencia:n(v) v S n(v) v t S
donde denota los sucesores de v , es decir, succ ( v ) = { w : v → w es una ventaja en S } , y donde tenemos el caso base n ( t ) = 1 .succ(v) v succ(v)={w:v→w is an edge in S} n(t)=1
A continuación, usamos la anotación para muestrear una ruta aleatoria. Primero visitamos el nodo s . Luego, elegimos aleatoriamente uno de los sucesores de s , con el sucesor w ponderado por n ( w ) . En otras palabras:n(⋅) s s w n(w)
Para elegir una ruta aleatoria, repetidamente repetimos este proceso: es decir, , y v i + 1 = ( v i ) . La ruta resultante es la ruta deseada, y se muestreará de manera uniforme al azar de todas las rutas más cortas de s a t .v0=s vi+1= (vi) s t
choosesuccessor
Esperemos que esto le ayude a comprender la solución de Realz Slaw más fácilmente. ¡Todo el crédito a Realz Slaw por la solución hermosa y limpia de este problema!
El único caso que esto no maneja es el caso en que algunos bordes tienen peso 0 o peso negativo. Sin embargo, el problema no está bien definido en ese caso, ya que puede tener infinitas rutas más cortas.
fuente