Alle Pfade mit weniger als einer bestimmten Länge in einem gerichteten Graphen zwischen mehreren Knoten

8

Das Zählen aller möglichen Pfade oder aller möglichen Pfade mit einer bestimmten Länge zwischen mehreren Knoten in einem gerichteten oder ungerichteten Graphen ist ein klassisches Problem. Aufgrund der möglichen Zyklen sollte darauf geachtet werden, was alles bedeutet.

Diese Frage ist etwas anders, oder zumindest denke ich.

EINGABE: Sei G ein gerichteter Graph. G kann Zyklen und auch selbstverbundene Knoten haben. Sei A (G) die Adjazenzmatrix von G (mit einer 1 in G i, j, wenn eine Verbindung von i nach j besteht, und andernfalls einer 0). Definieren Sie T und B zwei Teilmengen von Knoten von G , möglicherweise mit Hohlraumschnitt.

ERGEBNIS: Eine Liste aller Pfade mit einer Länge von höchstens k, die von einem Knoten in T zu einem Knoten in B führen . Pfade können mehrmals dieselben Kanten enthalten, solange sie in weniger als k + 1 Schritten vom Quellknoten zum Zielknoten gelangen.

FRAGE: Ich möchte wissen, welcher Algorithmus bei dieser Aufgabe am besten funktioniert. Ich versuche, eine mögliche Antwort zu entwickeln, die auf der Tatsache basiert, dass die n-te Potenz der Adjazenzmatrix, wenn sie symbolisch berechnet wird (mit einer anderen Variablen für jeden Eintrag anstelle einer 1), Spuren all dieser Pfade (und dieser) enthält reduziert sich auf die Zählung von Pfaden, wenn numerisch mit 1 in den Einträgen berechnet wird). Aber ich weiß wirklich nicht, ob dies der schnellste Weg ist, die Aufgabe zu erledigen (wahrscheinlich nicht).

CAVEAT: Ich frage weder nach dem Zählproblem noch nach den kürzesten Pfaden. Die Länge eines Pfades ist definiert als die Anzahl der verwendeten Kanten (Zählen der Wiederholung). Ich benutze R, aber wenn Sie es vorziehen, denken Sie in einer anderen Sprache darüber nach! Es tut mir wirklich leid, wenn die Frage bereits gestellt und gelöst wurde. Vielen Dank für die freundliche Hilfe!

Zusätzliche Informationen: Ich habe einen Matrix-Potenzreihen-Ansatz (A ^ 3 gibt alle 3 langen Pfade an, ...) und dfs / bfs ausprobiert. Ich denke, die beiden letzteren sind alles andere als optimal, da sie nicht berücksichtigen, dass ich an einer Reihe von Quellen und Zielen arbeite und daher viel überflüssige Arbeit verrichte ...

gvdr
quelle
Hallo! Sind Sie immer noch daran interessiert, die Matrizen symbolisch in R zu multiplizieren?
Ferdinand.kraft
Ja, obwohl es eher symbolisch ist (siehe die Frage im Stapelüberlauf). Vielen Dank.
gvdr
Dann sehen Sie meine Antwort bei Stackoverflow .
Ferdinand.kraft

Antworten:

7

Wenn mir an Ihrer Frage nichts fehlt, können Sie den Standardtrick anwenden, um die Frage nach mehreren Quellen und Zielen auf den Fall einer einzelnen Quelle und eines einzelnen Ziels zu reduzieren:

  1. Fügen Sie zwei neue Knoten und . st
  2. Verbinden Sie mit allen Quellen, s
  3. Verbinden Sie alle Ziele mit .t

Nach dieser Reduzierung befinden wir uns in der Standardfrageeinstellung mit zwei zusätzlichen Eckpunkten und und möchten Spaziergänge von bis einer Länge von höchstens .ststk+2

Kaveh
quelle
Wie konnte ich den Trick nicht sehen? Das macht einfach die Arbeit, nachdem alles ziemlich einfach zu sein scheint.
gvdr
1
Sie können den Matrix-Powering-Ansatz auch direkt für die ursprüngliche Adjazenzmatrix verwenden: ist die Anzahl der Pfade der Länge von bis . (Ak)ijkij
Yuval Filmus
@ YuvalFilmus, wie gesagt, ich zähle die Pfade nicht, sondern finde sie tatsächlich. Daher kann ich nicht einfach die Matrix-Stromversorgung verwenden, sondern eine "String" -Version davon.
gvdr
2
@ Yuval Filmus: Yuval ist richtig! Wenn er sich auf die "Anzahl der Pfade" bezieht, sollte dies nicht als Lösung für das Problem des Zählens verstanden werden, sondern nur, um zu wissen, welchen Index in der vorhergehenden Adjazenzmatrix . Wenn dann suche in dfs oder bfs rückwärts und untersuche alle Knoten genau dann if ebenfalls gleich 1Ak1(Ak)ij=1(Ak1)iω=1(Ak1)ωj
Carlos Linares López
Entschuldigung Carlos, ich habe deine Antwort verpasst.
gvdr