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 ...
Antworten:
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:
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 .s t s t k+2
quelle