Finden Sie alle Pfade zwischen Ursprungsziel mit Pfadlänge Einschränkung

Question

Ich benutze Python 2.7 und networkx.

Ich habe ein ziemlich großes Netzwerk und ich muss alle Wege (nicht nur den kürzesten Weg) zwischen einem Ursprung und einem Ziel finden. Da mein Netzwerk groß ist, möchte ich mit einigen Einschränkungen wie Pfadlänge, Kosten usw. beschleunigen.

Ich verwende networkx. Ich möchte nicht all_simple_paths verwenden, weil ich bei all_simple_paths alle Pfade später anhand der Pfadlänge (Anzahl der Knoten darin) oder der Kosten des Pfades (basierend auf den Lichtbogenkosten) filtern muss. Die Filterung aller Pfade ist für das große Netzwerk sehr teuer.

Ich würde wirklich jede Hilfe zu schätzen wissen.

Answer 1

Es hängt wirklich davon ab, welche Pfade Sie suchen.

Zunächst gibt der kürzeste Pfad die niedrigste Grenze c_min für die Längenbeschränkung an. Dann gibt es eine Längenbeschränkung c>=c_min, für jeden Knoten n, kennen Sie den kürzesten Pfad P_s_n und Abstand c_n von Anfang an diesen Knoten. Wählen Sie die Knoten, die c_n <c erfüllen. Dann können Sie P_s_n beliebig durch einen Pfad von n zu Ziel erweitern, die Ihre Längenbeschränkung erfüllen wird.