Effizientes Abtasten kürzester

Lassen ein Graph, und sei und zwei Eckpunkten sein . Können wir effizient einen kürzesten - - Pfad gleichmäßig und unabhängig von der Menge aller kürzesten Pfade zwischen und zufällig ? Der Einfachheit halber können wir annehmen, dass einfach, ungerichtet und ungewichtet ist.$G$$s$$t$$G$$s$$t$$s$$t$$G$

Selbst in vielen eingeschränkten Graphen kann die Anzahl der kürzesten Pfade zwischen und in der Größe von exponentiell sein . Deshalb möchten wir natürlich wie vermeiden Berechnung tatsächlich alle kürzesten - Pfade. Ich weiß nichts über den allgemeinen Fall, aber es scheint mir, dass wir dies für einige spezielle Grafikklassen erreichen können.$s$$t$$G$$s$$t$

Das fühlt sich an, als hätte jemand schon einmal darüber nachgedacht. Gibt es Forschungsergebnisse dazu oder ist dies sogar für allgemeine Grafiken einfach durchzuführen?

Ich bin nicht zu 100% sicher, dass diese Antwort richtig ist, aber hier ist:

Ich denke, Sie können dies in einer DAG mit einer einzigen Quelle und einer einzigen Senke auf gleichmäßig zufällige beliebige Pfade von reduzieren .$s-t$

Gegeben ein Diagramm $G$

1. Machen Sie einen neuen leeren digraph, .$H$
2. Erstens: das BFS Teil Dijkstra kürzesten Weg laufen, ausgehend von mit ihrem kürzesten Abstand-von- alle Knoten markieren s .$s$$s$
3. Sei der minimale Abstand von s - v ; Das wissen wir aus dem BFS-Schritt des Dijkstra-Algorithmus für kürzeste Wege.$d(s,v)$$s-v$
4. Führen Sie dann den nächsten Schritt des Dijkstra-Algorithmus für den kürzesten Pfad aus, ermitteln Sie den kürzesten Pfad und speichern Sie ihn in (indem Sie von t nach s zurückgehen ).$\mathbf p$$t$$s$
5. Starten Sie nun die folgende Schleife; Erklärung in Kommentaren und unten:
   • $q_0=\{t\}$
   • Während $q_0 \ne \emptyset$
     • $q_1= \emptyset$
     • Für $u \in q_0$
       • Wir wollen also alle möglichen nächsten Knoten für diesen kürzesten Unterpfad von $t-u$
       • Für alle so dass d ( s , v ) < d ( s , u $\text{edge}(u,v) \in G$$d(s,v) < d(s,u)$
         • ist ein benachbarter Knoten mit weniger d ( s , ⋅ ) (es wird 1 weniger sein)$v$$d(s,\cdot)$$1$
         • Daher ist ein möglicher Unterpfad auf einem kürzesten Pfad.$t-u-v$
         • Setzen Sie $v \rightarrow H, \text{di-edge}(u,v)\rightarrow H$
         • Jetzt müssen wir die Nachbarn von der nächsten Runde überprüfen .$v$
         • Setzen Sie $v \rightarrow q_1$
     • Setze auf q 1 : $q_0$$q_1$
       • $q_0 \leftarrow q_1$

Im Wesentlichen sammle ich alle möglichen Knoten , die in dem kürzesten Pfad verwendet werden können, und sie bei der Platzierung .$H$

Mehr darüber, wie das funktioniert:

Dijkstra Shortest-Path - Algorithmus arbeitet , indem zuerst ein BFS ausgeführt wird , und die Kennzeichnung aller Knoten mit ihren kürzesten Pfaden von s - v . Der nächste Schritt besteht darin, von t - s zurückzukehren und den am wenigsten benachbarten Knoten zu folgen.$v\in G$$s-v$$t-s$

Die Sache ist, hier können Sie einen der am wenigsten benachbarten Knoten auswählen . Was ich hier mache, ist, bei jedem Schritt alle am wenigsten benachbarten Knoten zu sammeln , was bedeutet, dass ich alle kürzesten Pfade erkläre.

Jetzt überlegst du schnell, aber hey, warum zählt du sie exponentiell auf, aber mein Weg ist es nicht?

Die Antwort lautet: Da ich ein Set verwende, um zu vermeiden, dass dieselben Knoten zweimal hinzugefügt werden, vermeide ich es, dies für jeden möglichen Pfad neu zu berechnen.

Jetzt haben wir eine DAG, die wir in beliebiger Weise von durchlaufen können , und erhalten einen kürzesten umgekehrten Pfad von $t-s$ . Das Diagramm sollte t als einzige Quelle und s als einzige Senke haben.$s-t$$t$$s$

Wenn das oben Gesagte zutrifft, können wir meines Erachtens noch einen Schritt weiter gehen und das Problem wie folgt lösen.

Geben Sie jedem Knoten in der DAG ein Knotengewicht. Das Knotengewicht ist die Anzahl der Pfade von diesem Knoten zu . Nennen wir dies w ( v ) .$s$$w(v)$

Sie können diese schnell berechnen, siehe Algorithmus, der die Anzahl der einfachen Pfade von s nach t in G ermittelt .

Sobald wir das Knotengewicht haben, können wir einen Pfad einheitlich auswählen, indem wir:

• Layout der DAG als Ebene-Struktur (zur Visualisierung)
• Wählen Sie auf jeder Ebene eine beliebige Reihenfolge zwischen den Knoten, z. ein Begriff von "von links nach rechts".
• Durchlaufen der DAG: Bei jedem Schritt , i ∈ [ 1 , | p | ] (wo$i$$i \in \left[1,\left|\mathbf p\right|\right]$ in diesem Fall die Länge des kürzesten Pfades bedeutet): $|\cdot|$
  • Sei der aktuelle Knoten (ab t )$u_i$$t$
  • Addiere alle Gewichte der Kinder von und wähle unter Verwendung eines RNG einen Kindknoten v i gleichmäßig zwischen den gewichteten Kindern.$u_i$$v_i$
  • Setze und gehe zum nächsten Schritt$u_{i+1} = v_i$

Hier ist eine Lösung, die auf den Ideen in der Antwort von Realz Slaw basiert. Es ist im Grunde eine Neuausstellung seiner Ideen, die klarer oder leichter zu befolgen sein könnte. Der Plan ist, dass wir in zwei Schritten vorgehen:

1. Zunächst erstellen wir einen Graphen mit der folgenden Eigenschaft: Jeder Weg von s nach t in S ist ein kürzester Weg von s nach t in G , und jeder kürzeste Weg von s nach t in G ist auch in S vorhanden . Somit enthält S genau die kürzesten Wege in G : alle kürzesten Wege und nichts weiter. Wie es passiert, wird S eine DAG sein.$S$$s$$t$$S$$s$$t$$G$$s$$t$$G$$S$$S$$G$$S$

2. Als nächstes werden wir alle Pfade von bis t in S gleichmäßig zufällig abtasten .$s$$t$$S$

Dieser Ansatz verallgemeinert sich auf einen willkürlich gerichteten Graphen , solange alle Kanten ein positives Gewicht haben. Deshalb erkläre ich meinen Algorithmus in diesen Begriffen. Sei w ( u , v ) das Gewicht an der Kante u → v . (Dies verallgemeinert die Problemaussage, die Sie gegeben haben. Wenn Sie ein ungewichtetes Diagramm haben, nehmen Sie einfach an, dass jede Kante das Gewicht 1 hat. Wenn Sie ein ungerichtetes Diagramm haben, behandeln Sie jede ungerichtete Kante ( u , v ) als die zwei gerichteten Kanten u → v und v → $G$$w(u,v)$$u \to v$$(u,v)$$u\to v$$v\to u$ .)

Schritt 1: Extrakt . $S$ Führen Sie einen Single-Source-Shortest-Path-Algorithmus (z. B. Dijkstra-Algorithmus) auf , beginnend mit Quelle s . Für jeden Eckpunkt v in G bezeichne d ( s , v ) den Abstand von s zu v .$G$$s$$v$$G$$d(s,v)$$s$$v$

Now define the graph $S$ as follows. It consists of every edge $u \to v$ such that (1) $u \to v$ is an edge in $G$, and (2) $d(s,v) = d(s,u) + w(u,v)$.

The graph $S$ has some convenient properties:

• Every shortest path from $s$ to $t$ in $G$ exists as a path in $S$: a shortest path $s=v_0,v_1,v_2,\dots,v_k=t$ in $G$ has the property that $d(s,v_{i+1})=d(s,v_i)+w(v_i,v_{i+1})$, so the edge $v_i \to v_{i+1}$ is present in $S$.

• Every path in $S$ from $s$ to $t$ is a shortest path in $G$. In particular, consider any path in $S$ from $s$ to $t$, say $s=v_0,v_1,v_2,\dots,v_k=t$. Its length is given by the sum of the weights of its edges, namely $\sum_{i=1}^k w(v_{i-1},v_i)$, but by the definition of $S$, this sum is $\sum_{i=1}^k (d(s,v_i)-d(s,v_{i-1})$, which telescopes to $d(s,t)-d(s,s)=d(s,t)$. Therefore, this path is a shortest path from $s$ to $t$ in $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:

where $\text{succ}(v)$ denotes the successors of $v$, i.e., $\text{succ}(v) = \{w : v \to w \text{ is an edge in $S$}\}$, and where we have the base case $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.