Skutecznie próbkuj najkrótsze ścieżki

Niech $G$ jest wykresem, niech $s$ i $t$ są dwa wierzchołki $G$ . Możemy skutecznie próbki najkrótszą $s$ - $t$ ścieżkę równomiernie i niezależnie losowo ze zbioru wszystkich najkrótszych ścieżek między $s$ i $t$ ? Dla uproszczenia możemy założyć, że $G$ jest prosty, nieukierunkowany i nieważony.

Nawet w ograniczonych wielu wykresów liczba najkrótszej ścieżki pomiędzy $s$ i $t$ mogą być wykładnicza o rozmiarze $G$ . Dlatego naturalnie chcielibyśmy uniknąć obliczania wszystkich najkrótszych ścieżek $s$ - $t$ . Nie wiem o ogólnym przypadku, ale wydaje mi się, że możemy to osiągnąć w przypadku niektórych specjalnych klas graficznych.

To wydaje się czymś, co ktoś musiał wcześniej rozważyć. Czy istnieją jakieś badania na ten temat, czy jest to w rzeczywistości łatwe do wykonania nawet dla ogólnych wykresów?

Nie jestem w 100% pewien, że ta odpowiedź jest poprawna, ale oto:

Myślę, że możesz sprowadzić to do jednakowo losowych dowolnych ścieżek, od , w DAG z jednym źródłem i jednym zlewem.$s-t$

Biorąc pod uwagę wykres $G$

1. Tworzy nowy pusty digraf, .$H$
2. Po pierwsze: uruchom część BFS najkrótszej ścieżki Dijkstry, zaczynając od , zaznacz wszystkie węzły ich najkrótszą odległością od s .$s$$s$
3. Niech będzie minimalną odległością od s - v ; które znamy z kroku BFS algorytmu najkrótszej ścieżki Dijkstry.$d(s,v)$$s-v$
4. Następnie wykonaj następny krok algorytmu najkrótszej ścieżki Dijkstry, uzyskaj najkrótszą ścieżkę, zapisz ją (przechodząc wstecz od t do s ).$\mathbf p$$t$$s$
5. Teraz uruchom następującą pętlę; wyjaśnienie w komentarzach i poniżej:
   • $q_0=\{t\}$
   • Podczas $q_0 \ne \emptyset$
     • $q_1= \emptyset$
     • Dla $u \in q_0$
       • Chcemy więc znaleźć wszystkie możliwe następne węzły dla tej najkrótszej podścieżki od $t-u$
       • Dla wszystkich takich, że d ( s , v ) < d ( $\text{edge}(u,v) \in G$$d(s,v) < d(s,u)$
         • jest sąsiednim węzłem o mniejszej liczbie d ( s , $v$ (będzie 1 mniej)$d(s,\cdot)$$1$
         • Dlatego jest możliwą podścieżką na najkrótszej ścieżce.$t-u-v$
         • Umieść $v \rightarrow H, \text{di-edge}(u,v)\rightarrow H$
         • Teraz musimy sprawdzić mniejszych sąsiadów następnej turze.$v$
         • Umieść $v \rightarrow q_1$
     • Ustaw na $q_0$ : $q_1$
       • $q_0 \leftarrow q_1$

Zasadniczo, jestem zbieranie wszystkich możliwych węzłów, które mogą być wykorzystane w najkrótszej ścieżce, i umieszczając je w .$H$

Więcej informacji o tym, jak to działa:

Algorytm najkrótszej ścieżki Dijkstry działa najpierw uruchamiając BFS i oznaczając wszystkie węzły ich najkrótszymi ścieżkami od s - v . Następnym krokiem jest powrót z t - s i podążenie za najmniej sąsiadującymi węzłami z powrotem.$v\in G$$s-v$$t-s$

Chodzi o to, że tutaj możesz wybrać jeden z najmniej sąsiadujących węzłów. To, co tu robię, to zbieranie wszystkich najmniej sąsiadujących węzłów na każdym kroku, co oznacza, że ​​uwzględniam wszystkie najkrótsze ścieżki.

Teraz szybko myślisz, ale hej, dlaczego wyliczasz je wykładniczo, ale moja droga nie jest?

Odpowiedź brzmi: ponieważ używam zestawu, aby uniknąć dodawania tych samych węzłów dwa razy, unikam ponownego obliczania tego dla każdej możliwej ścieżki.

Teraz mamy DAG, który możemy przejść w dowolny sposób z , i uzyskać najkrótszą odwróconą ścieżkę z s - t . Wykres powinien mieć t jako jedyne źródło, a $t-s$$s-t$$t$$s$ jako jedyne ujście.

Jeśli powyższe jest prawidłowe, myślę, że możemy pójść o krok dalej i rozwiązać problem w następujący sposób.

Nadaj każdemu węzłu w DAG wagę węzła; waga węzła będzie liczbą ścieżek od tego węzła do . Nazwijmy to w ( v $s$$w(v)$ .

Możesz je szybko obliczyć, patrz Algorytm, który znajduje liczbę prostych ścieżek od s do t w G .

Po uzyskaniu wagi węzła możemy jednolicie wybrać ścieżkę poprzez:

• Ułóż DAG jako strukturę poziomu (do wizualizacji)
• Na każdym poziomie wybierz dowolne uporządkowanie między węzłami, tj. pojęcie „od lewej do prawej”.
• Przechodzenie po DAG: na każdym kroku , i ∈ [ 1 , | p | ] (gdzie | ⋅ $i$$i \in \left[1,\left|\mathbf p\right|\right]$$|\cdot|$ oznacza rozmiar, w tym przypadku długości najkrótszej ścieżki):
  • Niech być obecny węzeł (rozpoczynając t )$u_i$$t$
  • Zsumuj wszystkie wagi dzieci używając RNG, wybierz jeden węzeł potomny, v i , równomiernie między ważonymi dziećmi.$u_i$$v_i$
  • Ustaw i przejdź do następnego kroku$u_{i+1} = v_i$

Oto rozwiązanie oparte na ideach zawartych w odpowiedzi Realza Slawa. Jest to w zasadzie ponowna prezentacja jego pomysłów, które mogą być jaśniejsze lub łatwiejsze do naśladowania. Plan jest taki, że będziemy postępować w dwóch krokach:

1. Najpierw zbudujemy wykres o następującej właściwości: każda ścieżka od s do t w S jest najkrótszą ścieżką od s do t w G , a każda najkrótsza ścieżka od s do$S$$s$$t$$S$$s$$t$$G$$s$ w G jest obecna w S . Zatem S zawiera dokładnie najkrótsze ścieżki w G : wszystkie najkrótsze ścieżki i nic więcej. Tak się składa, że S będzie DAG.$t$$G$$S$$S$$G$$S$

2. Następnie zostanie równomiernie próbki losowo wszystkich ścieżek z na T w S .$s$$t$$S$

To podejście uogólnia się na arbitralnie skierowany wykres , o ile wszystkie krawędzie mają dodatnią wagę, więc wyjaśnię mój algorytm w tych terminach. Niech w ( u , v ) oznacza ciężar na krawędzi u → v . (Uogólnia to podane przez ciebie stwierdzenie problemu. Jeśli masz nieważony wykres, po prostu załóż, że każda krawędź ma wagę 1. Jeśli masz niekierowany wykres, traktuj każdą nieukierowaną krawędź ( u , v ) jak dwie skierowane krawędzie u → v i v → u .)$G$$w(u,v)$$u \to v$$(u,v)$$u\to v$$v\to u$

Etap 1: Ekstrakt z . $S$ Uruchom algorytm najkrótszych ścieżek z jednego źródła (np. Algorytm Dijkstry) na , zaczynając od źródła s . Dla każdego wierzchołka v w G , niech d ( s , v ) oznacza odległość od s do $G$$s$$v$$G$$d(s,v)$$s$$v$ .

Teraz zdefiniuj wykres w następujący sposób. Składa się z każdej krawędzi u → v tak, że (1) u → v jest krawędzią w G , i (2) d ( s , v ) = d ( s , u ) + w ( u , v ) .$S$$u \to v$$u \to v$$G$$d(s,v) = d(s,u) + w(u,v)$

Wykres ma kilka dogodnych właściwości:$S$

• Każda najkrótsza ścieżka od do t w G istnieje jako ścieżka w S : najkrótsza ścieżka s = v 0 , v 1 , v 2 , … , v k = t w G ma właściwość, że d ( s , v i + 1 ) = d ( s , v i ) + w ( v i , v $s$$t$$G$$S$$s=v_0,v_1,v_2,\dots,v_k=t$$G$, dzięki czemu krawędź V i → V i + 1 jest obecny wS.$d(s,v_{i+1})=d(s,v_i)+w(v_i,v_{i+1})$$v_i \to v_{i+1}$$S$

• Każda ścieżka w z S na T jest najkrótsza ścieżka w G . W szczególności rozważ dowolną ścieżkę w S od s do t , powiedzmy s = v 0 , v 1 , v 2 , … , v k = t . Jego długość jest sumą wag jego krawędzi, a mianowicie ∑ k i = 1 w ( v i - 1 , v i$S$$s$$t$$G$$S$$s$$t$$s=v_0,v_1,v_2,\dots,v_k=t$$\sum_{i=1}^k w(v_{i-1},v_i)$, Ale z definicji , to suma Σ k i = 1 ( d ( S , V, I ) - d ( a , v I - 1 ) , które teleskopy D ( s , t ) - d ( s , s ) = d ( s , t ) . Dlatego ścieżka ta jest najkrótszą ścieżką od s do t w $S$$\sum_{i=1}^k (d(s,v_i)-d(s,v_{i-1})$$d(s,t)-d(s,s)=d(s,t)$$s$$t$$G$.

• Finally, the absence of zero-weight edges in $G$ implies that $S$ is a dag.

Step 2: sample a random path. Now we can throw away the weights on the edges in $S$, and sample a random path from $s$ to $t$ in $S$.

To help with this, we will do a precomputation to compute $n(v)$ for each vertex $v$ in $S$, where $n(v)$ counts the number of distinct paths from $v$ to $t$. This precomputation can be done in linear time by scanning the vertices of $S$ in topologically sorted order, using the following recurrence relation:

$\text{succ}(v)$$v$$\text{succ}(v) = \{w : v \to w \text{ is an edge in $S$}\}$$n(t)=1$.

Next, we use the $n(\cdot)$ annotation to sample a random path. We first visit node $s$. Then, we randomly choose one of the successors of $s$, with successor $w$ weighted by $n(w)$. In other words:

choosesuccessor(v):
    n = 0
    for each w in succ(w):
        n = n + n(w)
    r = a random integer between 0 and n-1
    n = 0
    for each w in succ(w):
        n = n + n(w)
        if r < n:
            return w

To choose a random path, we repeatedly iterate this process: i.e., $v_0=s$, and $v_{i+1} =$ choosesuccessor$(v_i)$. The resulting path is the desired path, and it will be sampled uniformly at random from all shortest paths from $s$ to $t$.

Hopefully this helps you understand Realz Slaw's solution more easily. All credit to Realz Slaw for the beautiful and clean solution to this problem!

The one case this doesn't handle is the case where some edges have weight 0 or negative weight. However, the problem is potentially not well-defined in that case, as you can have infinitely many shortest paths.